0

各要素が一度だけ使用されるリストから、サブセットのすべての組み合わせを見つけようとしています。

私の言いたいことを明確にするために、次の例のリストを示します。

[1、2、3、4]

次の組み合わせを生成できます。

[(1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)] (これは網羅的なはずです!)

次に、これらの組み合わせの組み合わせを生成できます。

[[(1), (2), (3)], [(1, 2), (3)], [(1, 3), (2)], [(1), (2, 3)] ,[(1, 2, 3)],... (多くの場合)]

要点は、特定の組み合わせで各要素を 1 回だけ使用できることです。だから私は持つことができません：

[(1), (1, 2, 3)] 要素 1 が 2 回使用されているためです。

私は小さな n (n < 10) に対してブルート フォースを試みてきましたが、Python を使用して失敗しています。この時点では、実行時の問題 (小さな n!) でさえありませんが、すべての可能性を見つけているわけではありません!

質問の仕方がよくわからないので、明確な質問をしてください。また、質問を明確にするのに役立つ特定のキーワードがある場合は、教えてください。私は Python のアプローチに興味がありますが、これを行うのに役立つあらゆる数学のアプローチを受け入れます。ランタイムは後で取り組みたい問題です。

ありがとう！

編集1:この質問を表示する別の方法は、サブセット合計の問題ですが、注意1:すべての可能なサブセットを見つけるだけでなく、元のリストの要素の最大数が使用されるように、サブセットの組み合わせのすべてのセットを見つけます。ここで、個々のサブセットの合計は 0 (または k) になります。

私の目標は、すべての回答をループし、最終的に使用されなかった要素の数に基づいてスコアを付け、サブセットの「最適な」セットを選択することです.

編集 2: 回答は受け入れられましたが、ユーザーが作成したリスト myList = ['a', 'b', 'c', 'd'] を受け入れるように変更されました

def partitions(myList):
   if not myList:
       yield []
   else:
       for partial_partition in partitions(myList[:-1]):
           for i in range(len(partial_partition)):
               copy_partition = partial_partition[:]
               copy_partition[i] += (myList[-1],)
               yield copy_partition
           yield partial_partition + [(myList[-1],)]
4

1 に答える 1

2

再帰！1..n のすべての可能なパーティションを生成し、それらを使用して 1..n+1 のすべての可能なパーティションを生成します。

def partitions(n):
    if n == 0:
        yield []
    else:
        for partial_partition in partitions(n-1):
            for i in range(len(partial_partition)):
                copy_partition = partial_partition[:]
                copy_partition[i] += (n,)
                yield copy_partition
            yield partial_partition + [(n,)]
于 2013-10-03T21:45:26.750 に答える