4

シーケンスをペアに分割し、それらを組み合わせて、組み合わせ内のすべての要素が一意になるようにする of 関数が必要です。Python の itertools を使用していくつかのアプローチを試みましたが、解決策が見つかりませんでした。

説明するために、次のシーケンスを取る関数が必要です: [1, 2, 3, 4]

次の 3 つの組み合わせに分割します。

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

より長いシーケンスでも機能するはずですが、奇数の長さのシーケンスを処理する必要はありません。例えば。

[1,2,3,4,5,6]

次の 15 の組み合わせに分割されます。

[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 6], [4, 5]]
[[1, 3], [2, 4], [5, 6]]
[[1, 3], [2, 5], [4, 6]]
[[1, 3], [2, 6], [4, 5]]
[[1, 4], [2, 3], [5, 6]]
[[1, 4], [2, 5], [3, 6]]
[[1, 4], [2, 6], [3, 5]]
[[1, 5], [2, 3], [4, 6]]
[[1, 5], [2, 4], [3, 6]]
[[1, 5], [2, 6], [3, 4]]
[[1, 6], [2, 3], [4, 5]]
[[1, 6], [2, 4], [3, 5]]
[[1, 6], [2, 5], [3, 4]]

... 等々。

Maple と呼ばれる CAS には、この関数がsetpartitionという名前で実装されています。

編集：wksによって指摘された重大な深夜の入力エラーを修正し、出力を明確にしました。

4

3 に答える 3

5

itertools本当にあなたの友達です：

from itertools import permutations

def group(iterable, n=2):
    return zip(*([iter(iterable)] * n))

for each in permutations([1, 2, 3, 4, 5, 6]):
    print map(list, group(each))

結果：

[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 4], [6, 5]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 5], [6, 4]]
[[1, 2], [3, 6], [4, 5]]
[[1, 2], [3, 6], [5, 4]]
[[1, 2], [4, 3], [5, 6]]
[[1, 2], [4, 3], [6, 5]]
[[1, 2], [4, 5], [3, 6]]
...

[編集] @FrederikNS: 質問を明確にして自分で答えを見つけた後、ここに私の解決策があります:

from itertools import combinations

def setpartition(iterable, n=2):
    iterable = list(iterable)
    partitions = combinations(combinations(iterable, r=n), r=len(iterable) / n)
    for partition in partitions:
        seen = set()
        for group in partition:
            if seen.intersection(group):
                break
            seen.update(group)
        else:
            yield partition

for each in setpartition([1, 2, 3, 4]):
    print each
print
for each in setpartition([1, 2, 3, 4, 5, 6]):
    print each

結果：

((1, 2), (3, 4))
((1, 3), (2, 4))
((1, 4), (2, 3))

((1, 2), (3, 4), (5, 6))
((1, 2), (3, 5), (4, 6))
((1, 2), (3, 6), (4, 5))
((1, 3), (2, 4), (5, 6))
((1, 3), (2, 5), (4, 6))
((1, 3), (2, 6), (4, 5))
((1, 4), (2, 3), (5, 6))
((1, 4), (2, 5), (3, 6))
((1, 4), (2, 6), (3, 5))
((1, 5), (2, 3), (4, 6))
((1, 5), (2, 4), (3, 6))
((1, 5), (2, 6), (3, 4))
((1, 6), (2, 3), (4, 5))
((1, 6), (2, 4), (3, 5))
((1, 6), (2, 5), (3, 4))
于 2012-05-12T23:50:01.587 に答える
1

私はついにそれを自分で手に入れました（ピルマンチャーの答えは本当に正しい方向に私を動かしてくれました、そしてグループ機能は完全に彼のものです）：

def group(iterable, n=2):
    return zip(*([iter(iterable)] * n))

def set_partition(iterable, n=2):
    set_partitions = set()

    for permutation in itertools.permutations(iterable):
        grouped = group(list(permutation), n)
        sorted_group = tuple(sorted([tuple(sorted(partition)) for partition in grouped]))
        set_partitions.add(sorted_group)

    return set_partitions

partitions = set_partition([1,2,3,4], 2)
for part in partitions:
    print(part)

これは印刷します：

((1, 4), (2, 3))
((1, 3), (2, 4))
((1, 2), (3, 4))
于 2012-05-13T09:54:51.987 に答える
-1

これを試して：

def function(list):
    combinations = []
    for i in list:
        for i2 in list:
            if not [i2, i] in combinations:
                 combinations.append([i, i2])
    return combinations

これにより、可能なすべての組み合わせが返されます。

お役に立てれば！

于 2012-05-12T23:47:34.890 に答える