[pgs偽装]リストにXを追加して組合せを得る

プログラマーを偽装する

itertools.combinations

from itertools import combinations

これはソートやコンビネーション,確率などを学習する際に現れるコンビネーションを表す方法である.「headgear」「メガネ」「靴」の中から2つを抜き取ると、3つのケースが発生します.単純に組合せ(list,2)として実現できる.
下図に示すように、tuple形式でペアをなす2つのデータはitertools形式で含まれる.使用を続行できるのは、リストにリストされている場合のみです.そうしないとiterは回転すると消えてしまいます

Question

これはすべての状況を数える問題です.

Solution

Solution 1

PSEUDO

count dictを作成します.
ex){帽子:2種,靴:3種,シャツ:2種}

キー(服装種類)で組み合わせを抽出します.可能なすべての数をレビューします.
ex)3種類あれば、3 C 1、3 C 2、3 C 3

.

のすべての組合せに対して、各count個数を乗じた値を取り、すべての値を加えて答えを求める.
ex)(帽子、靴)、帽子2種類靴3種類の場合、この組み合わせは2*3種類で

という意味です

from itertools import combinations as cbs
def sol_1(clothes):
    # make dict
    vocab = dict()
    for name, cat in clothes:
        if cat not in vocab:
            vocab[cat] = 1
        else:
            vocab[cat] += 1
    
    ans = 0
    for num in range(1, len(vocab)+1):
        for com in list(cbs(vocab, num)):
            temp = 1
            for c in com:
                temp *= vocab[c]
            ans += temp
    return ans

Solution 2

方法が少し違うと,問題はすぐ解決した.プログラミングの問題というより、思考テスト...
PSEUDO

同様にcount dictを作成し、

の各count(value)に+1を乗算した.

回答この値-1で

どうしたんですか.次のように考えましょう.右のようにX(着なければ)を加え、自然とハトやシャツ、靴などしか着ません.(A、D、X)、(X、X、G)など.そして最後に-1をするのは、すべてのXを選択した場合を削除しなければならないからです.非常に簡単にO(n)で解くことができる.

def sol_2(clothes):
    vocab = dict()
    for name, cat in clothes:
        if cat in vocab:
            vocab[cat] += 1
        else: vocab[cat] = 1
    ans = 1
    for i in vocab.values():
        ans *= (i+1)
    return ans-1

ソリューション1では、1つのケースでタイムアウトが発生し、2つのコードの時間効率の違いが一目でわかります.もし時間を超えたら、私は頭で他の人に近づきます.


github