45

私はの配列を持っています[1,2,3]

配列のすべての要素を使用して、可能なすべての組み合わせを作成したい:

結果：

[[1], [2], [3]]
[[1,2], [3]]
[[1], [2,3]]
[[1,3], [2]]
[[1,2,3]]
4

5 に答える 5

11

私のコメントが示唆したのとは異なり、私は itertools ベースの比較的高速なソリューションをすぐに見つけることができませんでした! 編集：これはもはや真実ではありません。私は itertools を主に使用したかなり短い（しかし遅くて読めない）ソリューションを持っています。答えの最後を見てください。これは私が代わりに得たものです：

アイデアは、合計がリストの長さになる整数のすべての組み合わせを見つけ、その長さのスライスを含むリストを取得するというものです。

たとえば、長さ 3 のリストの場合、組み合わせまたはパーティションは (3)、(2, 1)、(1, 2)、および (1, 1, 1) です。したがって、リストの最初の 3 つの項目を返します。最初の 2、次に次の 1。最初の 1、次の 2、最初の 1、次の 1、次の 1。

hereから整数パーティショニングのコードを取得しました。ただし、パーティション関数はパーティションのすべての順列を返すわけではありません (つまり、3 の場合は (3)、(2, 1)、および (1, 1, 1) を返すだけです)。そのためitertools.permutations、パーティションごとに呼び出す必要があります。重複を削除する簡単な方法は、タプルの各リストを に変換することpermutations([1, 2, 3])です[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。permutations([1, 1, 1])[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]]set

あとは、タプルの長さのリストのスライスを取得するだけです。たとえばf([1, 2, 3], [0, 0, 1, 2, 1, 0])、 に行き[[0], [0, 1], [2, 1, 0]]ます。

それについての私の定義は次のとおりです。

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

すべてを組み合わせるだけです。

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

>>> for i in subgrups(my_list):
        print(i)

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

また、プログラムの先頭でも実行する必要がありimport itertoolsます。from copy import deepcopy

編集:あなたの与えられた出力は不明です。私はあなたが私があなたに与えた機能を望んでいたと思いましたが、あなたの出力には も含まれています[[1,3],[2]]. .[[1, 2], [3]][[1, 2], 3]

つまり、出力として与えるつもりだったのは次のとおりだと思います。

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

実際にこれだった場合：

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
[[1], [3], [2]]
[[1], [3, 2]]
[[1, 3], [2]]
[[1, 3, 2]]
[[2], [1], [3]]
[[2], [1, 3]]
[[2, 1], [3]]
[[2, 1, 3]]
[[2], [3], [1]]
[[2], [3, 1]]
[[2, 3], [1]]
[[2, 3, 1]]
[[3], [1], [2]]
[[3], [1, 2]]
[[3, 1], [2]]
[[3, 1, 2]]
[[3], [2], [1]]
[[3], [2, 1]]
[[3, 2], [1]]
[[3, 2, 1]]

subgrups次に、元のリストの 3 つの長さの順列ごとに、たとえば の順列ごとに呼び出すだけですitertools.permutations(my_list, len(my_list))。

itertools編集：短いベースのソリューションの私の約束を守るために。警告 - 読み取り不能で遅い可能性があります。

まずslice_by_lengths、これを次のように置き換えます。

def sbl(lengths, the_list):
    for index, length in enumerate(lengths):
        total_so_far = sum(lengths[:index])
        yield the_list[total_so_far:total_so_far+length]

次に、この回答から、整数分割関数を取得します。

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

この関数は、実際には整数パーティションのすべての順列を取得するため、必要ありません。

for each_partition in partitions:
    permed.append(set(itertools.permutations(each_partition, len(each_partition))))

もう。ただし、再帰的であるため (そして Python で実装しているため)、以前のものよりもはるかに遅くなります。

次に、それをまとめます。

def subgrups(my_list):
    for each_tuple in partition(len(my_list)):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

または読みにくいですが、関数定義はありません:

def subgrups(my_list):
    for each_tuple in (lambda p, f=lambda n, g:
                          {(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}:
                              f(p, f))(len(my_list)):
        yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))

これは関数定義と 2 行であり、最初に述べた内容にかなり近いものです (ただし、読みにくく、処理速度も大幅に低下します)。

(subgrups質問が最初に「すべてのサブグループ」を見つけるように求められたために呼び出される関数)

于 2013-10-14T21:13:19.913 に答える
0

再帰の代わりにループを使用するように、アレクシスの回答を変換しました。コードは理解するのが簡単ではありませんが、非常に大きなセットでも動作するはずです:

def partition(collection: Sequence[T]) -> List[List[List[T]]]:
    collection_except_last = reversed(collection[:-1])
    only_last = list(collection[-1:])

    # start with the partition for a 1-element collection and then add elements
    partitions = [[only_last]]
    for element in collection_except_last:
        refined_partitions: List[List[List[T]]] = []
        for partition_ in partitions:
            # insert `element` in each of the subpartition's subsets
            for n, subset in enumerate(partition_):
                refined = partition_[:n] + [[element] + subset] + partition_[n + 1 :]
                refined_partitions.append(refined)
            # put `element` in its own subset
            refined_partitions.append([[element]] + partition_)
        partitions = refined_partitions
    return partitions
于 2022-02-20T16:47:09.103 に答える