Python で配列の可能なすべてのセット パーティションを生成するにはどうすればよいですか?

Python でパーティションを設定する

配列を個別のサブセットに分割し、各要素が 1 つのサブセットにのみ属することは、セット パーティショニングと呼ばれます。要素の配列が与えられた場合、Python を使用してすべての可能なセット パーティションを生成するにはどうすればよいでしょうか?

配列 [1, 2, 3] について考えてみましょう。次のパーティションを取得することを目的としています。

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

再帰的ソリューション

私たちのソリューションは、再帰を活用してこのパーティション化を実現します。 n-1 個の要素のパーティションの場合、n 番目の要素を収容するための 2 つのオプションを検討します。

1. n 番目の要素を既存のサブセットに追加する。
2. 要素のみを含む新しいサブセットを作成する。 n 番目の要素。

これらのオプションを繰り返し適用することで、可能なすべてのパーティションを構築できます。

実装

<code class="python">def partition(collection):
    if len(collection) == 1:
        yield [collection]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # Insert first into existing subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n+1:]
        # Create a new subset
        yield [[first]] + smaller


something = list(range(1, 5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))</code>

出力

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

このソリューションは、指定された配列のすべての可能なセット パーティションを効果的に生成します。

以上がPython で配列の可能なすべてのセット パーティションを生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。