プログラマ偽装

に見せかける
問題の説明
スパイたちは毎日違う服を着て自分を偽装している.
例えば、スパイの服が以下のように、今日スパイが丸い眼鏡、長いコート、青いTシャツを着ている場合は、翌日はジーンズを追加したり、黒いサングラスをかけたりして、丸い眼鏡ではありません.
スパイが持っている服に二次元配列の服が与えられた場合、異なる服の組み合わせの数を返すために解関数を作成します.
顔が丸いメガネ、黒いサングラスに青いTシャツのジーンズコートロングコート
せいげんじょうけん

服装の各行は「服装名、服装種類」からなる.

スパイが持っている服の数は1着以上30着以下.

のような名前の服は存在しません.

アパレルのすべての要素は文字列から構成されています.

すべての文字列の長さは、1または20未満の自然数であり、アルファベット小文字または「」のみから構成されます.

スパイは毎日少なくとも1枚の服を着ている.

I/O例
clothesreturn[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]5[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]3
I/O例説明

例#1
headgearに対応した服装は黄色hat、緑turban、眼鏡に対応した服装は青サングラスで、以下の5つの組み合わせが可能です.

yellow_hat

blue_sunglasses

green_turban

yellow_hat + blue_sunglasses

green_turban + blue_sunglasses

concept
私がこの問題に触れたとき、それはきっと部分集合だと思います.
正直I/Oの例を見て理解しました.
もし服が3種類あるならば、1種類着ることができて、もし+2種類着ることができるならば、+3種類着ることができて、=return
このような事故は頭を支配した.
#1.だから...まず服の種類数を要求し、ディックシャーキャンプの形で実現する(この場合value値は服の詳細情報を必要としないので...)bit演算で部分集合の個数を求めて、もう一度します.
#2.次に、、、部分セットの作成が遅すぎますか...?内蔵の組み合わせを利用すると思いますが、おでこも...実行タイムアウト->itertools importの組合せをインポートして作成する必要があります.
#3.部分集合で解決する問題ではないようですので、実行時間を考えて、もう一度考えてみましょう.
そして高校时代に学んだ数学.
すべての服の種類に＋「何も着ない」という条件をつけて、何も着ていない場合を除けばいいのです.
一般的に3枚の服と下2枚の服を合わせて6種類の服を組み合わせることができます.
上の胃腸の問題を試してみると、3+2+6=11種類あるはずです.
それを3着+着ない(1)下衣2着+着ない(1)と考えると12種類出てきますが、
ここで上下とも着ていない場合は、1を外すと11種類の答えが見つかります.
code#1

def solution(clothes):
    dic = {}
    for wear in clothes:
        if(wear[1] not in dic):
            dic[wear[1]] = 1
        else:
            dic[wear[1]] += 1
    
    wear = list(dic.keys())
    num = len(wear)
    answer = 0

    for n in range(1,num+1):
        for i in range(1<<num):
            if(bin(i).count('1')!=n):
                continue
            sum = 1
            for j in range(num):
                if(i & 1 << j):
                    sum *= dic[wear[j]]
                answer += sum
    return answer

このようなフレームワークがあり,部分集合の総数=2^集合の大きさを知る.
すべての部分集合については,00000~111111が存在し,各バイナリ数の位置を部分集合のインデックスと見なせば容易に理解できる.
とにかくこういう方法で書いてあります…!実行タイムアウト...すべての部分集合を探索するのに多くの時間がかかったようだ.
code#2

from import combinations

def solution(clothes):
    dic = {}
    for wear in clothes:
        if(wear[1] not in dic):
            dic[wear[1]] = 1
        else:
            dic[wear[1]] += 1
    
    wear = list(dic.keys())
    num = len(wear)
    answer = 0

    for i in range(1,num+1):
        c = combinations(wear,i)
        for c_set in c:
            sum = 1
            for a in c_set:
                sum *= dic[a]
            answer += sum
    return answer

code#3

# 위장
from itertools import combinations

def solution(clothes):
    dic = {}
    for wear in clothes:
        if(wear[1] not in dic):
            dic[wear[1]] = 2
        else:
            dic[wear[1]] += 1
    answer = 1
    for val in dic.values():
        answer*=val
    answer-=1
    return answer

リファレンス
数学の問題...