6

これは私が思いついたコードです：

def combinations(input):
    ret = ['']
    for i in range(len(input)):
        ret.extend([prefix+input[i] for prefix in ret])
    return ret

このアルゴリズムはO（2 ^ n）時間ですが、スペースを減らすことはできますか？を使用するとうまくいくかもしれないと聞きましたyieldが、を使用して実装する方法を考えるのに苦労していyieldます。組み込みの組み合わせ関数は使用しないでください。どのように実装されているかを確認したいと思います。

4

3 に答える 3

6

あなたの質問は、コードがどのように見えるかを見たいと具体的に言っていたので、ここにO（n）スペースソリューションの手書きの例があります：

def combinations(input_list, acc=''):

    if not input_list:
        yield acc
        return

    next_val = input_list[0]

    for rest in combinations(input_list[1:], acc):
        yield rest

    acc += next_val

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)"
    for rest in combinations(input_list[1:], acc):
        yield rest

部分文字列の演算は（文字列を何度もコピーする必要があるため）コストがかかる可能性があるため、複雑さの点で少し効率的なバージョンを次に示します。

def combinations(input_list, acc='', from_idx=0):

    if len(input_list) <= from_idx:
        yield acc
        return

    next_val = input_list[from_idx]

    for rest in combinations(input_list, acc, from_idx + 1):
        yield rest

    acc += next_val

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)"
    for rest in combinations(input_list, acc, from_idx + 1):
        yield rest

私はPython3.2を使用していませんが、もしあなたがそうなら、次のように書くことができます：

def combinations(input_list, acc='', from_idx=0):

    if len(input_list) <= from_idx:
        yield acc
        return

    next_val = input_list[from_idx]

    yield from combinations(input_list, acc, from_idx + 1)
    acc += next_val
    yield from combinations(input_list, acc, from_idx + 1)

また、これは純粋に学術的なものであることに注意する必要があります。これはitertools.combinations、優れた仕事をし、より幅広い入力（ジェネレーター式を含む）で機能するためです。

于 2012-04-12T01:24:53.423 に答える
3

yield次のようにコードで使用できます。

def combinations(input):
    ret = ['']
    yield ''
    for i in range(len(input)):
        for prefix in ret:
             combination = prefix+input[i]
             ret.extend(combination)
             yield combination

しかし、それはあなたにどんなスペースも節約しません。

itertools.combinationsのドキュメントは、一定の空間で機能する（はるかに）より複雑なアルゴリズムを示しています。実際の実装はCですが、同等であると主張しています。

于 2012-04-12T01:36:10.707 に答える
1

このような何かがそれを行う必要があります：

>>> print list(itertools.combinations({1, 2, 3, 4}, 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
>>>
于 2012-04-12T00:54:30.540 に答える