Pythonで配列分割パターンの全通り列挙

Question

前提・実現したいこと

Pythonで配列を2つに分けたときの全通りをリストする機能はありますでしょうか。

例：
[1,2,3,4]を渡したときに
[
[[1,2],[3,4]],
[[1,3],[2,4]],
[[1,4],[2,3]]
]

を取得したいです。
数字の重複は発生しません。

numpy.splitは前後でしか分割できないようです。

補足情報（FW/ツールのバージョンなど）

Python 3.7.3
を使用しています。

Comments

[kirara0048]

要素数が奇数の場合はどうなりますか？

[Py_pp]

すみません、要素数は偶数のみの想定でお願いします

Answer 1

以下のようにできます。

1. 2つのグループにおおよそ等しく分割するとする。

例: 要素数4 -> 2個、2個、要素数5 -> 2個、3個

1. itertools.combinations で一方のグループのパターン (g1 とする) を列挙
2. 配列から g1 を除いた要素がもう一方のグループ g2 となる。
3. (g1, g2) の組み合わせから重複するものは削除する。

例: ((1, 2), (3, 4)) と ((3, 4), (1, 2)) は同じ
4.1. まずグループをソートする。g1, g2 if g1 < g2 else g2, g1
例: ((1, 2), (3, 4)) も ((3, 4), (1, 2)) もソート後は ((1, 2), (3, 4)) になる。
4.2. set() で重複を消す。

from itertools import combinations


def split(array):
    n_group1 = len(array) // 2  # 2つのうち、一方のグループの個数

    g1 = list(combinations(array, 2))  # グループ1
    print(g1)  # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

    g2 = [tuple(set(array) - set(x)) for x in g1]  # グループ2
    print(g2)  # [(3, 4), (2, 4), (2, 3), (1, 4), (1, 3), (1, 2)]

    # 重複を除いた組み合わせ
    pairs = set((x, y) if x < y else (y, x) for x, y in zip(g1, g2))
    pairs = list(pairs)
    
    return pairs

array = [1, 2, 3, 4]

pairs = split(array)
print(pairs)  # {((1, 3), (2, 4)), ((1, 4), (2, 3)), ((1, 2), (3, 4))}

Comments

[kirara0048]

一行にしてみました
pairs = [(x, tuple(set(array) - set(x))) for x in combinations(array, len(array)//2) if len(array)%2 or array[0] == x[0]]

[kirara0048]

あと`set(array) - set(x)` は `set(array).difference(x)` の方がよさそうですね

[tiitoi]

kirara0048 さん
1行で書くなら、そのような書き方もできますね。
コメントありがとうございます。

Answer 2

組合せを使った方法です。
理想よりも２倍の列挙（走査）数かかりますが、結果は得られます。

import itertools

lst = [1,2,3,4]
d = {}
s = set(lst)
for c in itertools.combinations(s, 2):

    t1 = tuple(sorted(c))          # 取ったもの
    t2 = tuple(sorted(s - set(c))) # 残ったもの

    # 小さいほうをキーとして重複を取り除く
    k,v = (t1, t2) if t1 < t2 else (t2, t1)
    d[k] = v

for k,v in d.items():
    print(k,v)
#(1, 2) (3, 4)
#(1, 3) (2, 4)
#(1, 4) (2, 3)