グループの長さとグループ内のすべての可能な組み合わせでリストをn個のグループに分割する方法は？

Question

リストをすべての可能な組み合わせでn個のグループに分割したい（可変グループ長を許す）。

言って、私は次のリストがあります。私が指定n = 2の場合

lst=[1,2,3,4] 

を、リストのいずれか1素子3の要素または2つの要素-2要素のグループに分割することができます。リストを分割するこれらの2つの方法の中には、各リストにどの要素が入るかというユニークな組み合わせがあります。

有するN = 2、これらは次のようになります

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

有するN = 1これらは、次のようになります

(1,2,3,4) 

とを有するn = 3これらは次のようになります。

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

私は長さ0のグループに興味がなく、グループ内の順序は関係ありません。

私は2つの同様の質問を見つけましたが、私の質問に正確に答えません。

This質問は、各グループの長さがn（@toklandの回答がわかりました）のすべての組み合わせにリストを分割します。しかし、私はすべてのグループが同じ長さであることを望んでいません。

次に、this質問の最初のステップでは、リストをn個のグループに分割するための分割位置の固有の組み合わせが得られます。ただし、ここではリストの順序が保持され、これらのグループ内の要素の一意の組み合わせは決定されません。

私は、これらの2つの質問の組み合わせを探しています。リストは、グループ長とグループ内の要素の組み合わせのすべての可能な組み合わせでn個のグループに分割されています。

Answer 1

我々はthis answerから基本的な再帰アルゴリズムを使用して生成し、不要なパーティションを除外することなく、特定の長さのパーティションを生成するためにそれを変更することができます。

def sorted_k_partitions(seq, k): 
    """Returns a list of all unique k-partitions of `seq`. 

    Each partition is a list of parts, and each part is a tuple. 

    The parts in each individual partition will be sorted in shortlex 
    order (i.e., by length first, then lexicographically). 

    The overall list of partitions will then be sorted by the length 
    of their first part, the length of their second part, ..., 
    the length of their last part, and then lexicographically. 
    """ 
    n = len(seq) 
    groups = [] # a list of lists, currently empty 

    def generate_partitions(i): 
     if i >= n: 
      yield list(map(tuple, groups)) 
     else: 
      if n - i > k - len(groups): 
       for group in groups: 
        group.append(seq[i]) 
        yield from generate_partitions(i + 1) 
        group.pop() 

      if len(groups) < k: 
       groups.append([seq[i]]) 
       yield from generate_partitions(i + 1) 
       groups.pop() 

    result = generate_partitions(0) 

    # Sort the parts in each partition in shortlex order 
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result] 
    # Sort partitions by the length of each part, then lexicographically. 
    result = sorted(result, key = lambda ps: (*map(len, ps), ps)) 

    return result 

ここではかなり多くのことが説明されています。

まず、我々は同じaforementioned recursive algorithmの手続き、ボトムアップ（？teminology）実装を開始します。

def partitions(seq): 
    """-> a list of all unique partitions of `seq` in no particular order. 

    Each partition is a list of parts, and each part is a tuple. 
    """ 
    n = len(seq) 
    groups = [] # a list of lists, currently empty 

    def generate_partitions(i): 
     if i >= n: 
      yield list(map(tuple, groups)) 
     else: 
      for group in groups 
       group.append(seq[i]) 
       yield from generate_partitions(i + 1) 
       group.pop() 

      groups.append([seq[i]]) 
      yield from generate_partitions(i + 1) 
      groups.pop() 

    if n > 0: 
     return list(generate_partitions(0)) 
    else: 
     return [[()]] 

メインアルゴリズムは、ネストされたgenerate_partitions機能です。基本的に、それはシーケンスを通って歩き、各アイテムについて、それは：1）そのアイテムをワーキングセット内の現在のグループ（a.k.aパーツ）のそれぞれに入れて再帰する。 2）アイテムをそれ自身の新しいグループに入れます。

シーケンス（i == n）の最後に到達すると、私たちが構築している作業セットの（深い）コピーが得られます。

ここで、特定の長さのパーティションを取得するには、はとなります。これは、探しているものに対して結果をフィルタリングまたはグループ化するだけですが、このアプローチでは多くの不必要な作業私たちがちょうどある長さの区画を望むならば、それはkです。上記の関数で、パーティションの長さ（基すなわち＃）がたびに増加する

注

  # this adds a new group (or part) to the partition 
      groups.append([seq[i]]) 
      yield from generate_partitions(i + 1) 
      groups.pop() 

は...実行されます。したがって、我々は単純にそうように、そのブロックの上にガードを置くことによって、パーティションのサイズを制限：新しいパラメータとpartitions機能にちょうどその行を追加する

def partitions(seq, k): 
    ... 

    def generate_partitions(i): 
     ... 

      # only add a new group if the total number would not exceed k 
      if len(groups) < k: 
       groups.append([seq[i]]) 
       yield from generate_partitions(i + 1) 
       groups.pop() 

今だけの長さのパーティションを生成することが発生しますまでk。これはほとんど私たちが望むものです。問題は、forループが長さがで、kより小さいパーティションを生成することがあることです。

これらの再帰的ブランチを削除するには、作業セットを合計でk個のグループに拡張するのに十分な残りの要素があることが確認できるときには、forループを実行する必要があります。残りの要素またはまだグループに配置されていない要素の数はn - i（またはlen(seq) - i）です。 k - len(groups)は、有効なkパーティションを作成するために追加する必要がある新しいグループの数です。 n - i <= k - len(groups)の場合は、はには現在のグループの1つを追加してアイテムを捨てることはできません。はに新しいグループを作成する必要があります。

だから我々は単に別のガードを追加し、他の再帰的なブランチにこの時間：

def generate_partitions(i): 
     ... 

      # only add to current groups if the number of remaining items 
      # exceeds the number of required new groups. 
      if n - i > k - len(groups): 
       for group in groups: 
        group.append(seq[i]) 
        yield from generate_partitions(i + 1) 
        group.pop() 

      # only add a new group if the total number would not exceed k 
      if len(groups) < k: 
       groups.append([seq[i]]) 
       yield from generate_partitions(i + 1) 
       groups.pop() 

そして、それとは、あなたが取り組んでK-パーティション発電機を持っています。再帰呼び出しの一部をさらに崩壊させる可能性があります（たとえば、残りのアイテムが3つあり、さらに3つのグループが必要な場合は、各アイテムをそれぞれのグループに分割する必要があることをすでに知っています）。すべてのパーティションを生成する基本的なアルゴリズムのわずかな変更として機能します。

残っているのは、結果を並べ替えることだけです。残念ながら、望ましい順序でパーティションを直接生成する方法（よりスマートな犬のためのエクササイズ）を考え出すのではなく、私は騙されてポストジェネレーションをソートしました。

def sorted_k_partitions(seq, k): 
    ... 
    result = generate_partitions(0) 

    # Sort the parts in each partition in shortlex order 
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result] 
    # Sort partitions by the length of each part, then lexicographically. 
    result = sorted(result, key = lambda ps: (*map(len, ps), ps)) 

    return result 

キー機能を除いて、やや自明です。最初の1：

key = lambda p: (len(p), p) 

は、（Pythonでは、デフォルトで辞書順順序付けられている、）配列自体によって、長さのシーケンスをソートすると言います。 pは「部品」の略です。これは、パーティション内のパーツ/グループをソートするために使用されます。このキーは、たとえば(4,)が(1, 2, 3)に先行するので、[(1, 2, 3), (4,)]が[(4,), (1, 2, 3)]とソートされることを意味します。

key = lambda ps: (*map(len, ps), ps) 
# or for Python versions <3.5: lambda ps: tuple(map(len, ps)) + (ps,) 

ここpsは、複数の "部" の略です。これは、各要素の長さ（シーケンス自体でなければならない）でシーケンスをソートし、次にシーケンス自体によって（辞書的に）並べ替えると言います。これは、パーティションをお互いに並べ替えるために使用されます。たとえば、[(4,), (1, 2, 3)]が[(1, 2), (3, 4)]に先行するようにします。

次

seq = [1, 2, 3, 4] 

for k in 1, 2, 3, 4: 
    for groups in sorted_k_partitions(seq, k): 
     print(k, groups) 

は生成します。

1 [(1, 2, 3, 4)] 
2 [(1,), (2, 3, 4)] 
2 [(2,), (1, 3, 4)] 
2 [(3,), (1, 2, 4)] 
2 [(4,), (1, 2, 3)] 
2 [(1, 2), (3, 4)] 
2 [(1, 3), (2, 4)] 
2 [(1, 4), (2, 3)] 
3 [(1,), (2,), (3, 4)] 
3 [(1,), (3,), (2, 4)] 
3 [(1,), (4,), (2, 3)] 
3 [(2,), (3,), (1, 4)] 
3 [(2,), (4,), (1, 3)] 
3 [(3,), (4,), (1, 2)] 
4 [(1,), (2,), (3,), (4,)] 

Answer 2

@friendly_dogからの有用なリンクに続いて、私はthis投稿で使用されている機能を調整して自分自身の質問に答えようとしています。私はそれが特に効率的ではないといくつかの改善を使用する恐れがありますが、私は、動作するような荒い解決策があります。私は必要以上に多くのパーティションを生成してしまい、ソート順だけが異なるものは除外します。

まず、私はSet partitions in Pythonからこれらの3つの機能を取る：

import itertools 
from copy import deepcopy 

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 partition(number): 
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)} 

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))) 

私はその後、subgrups機能をラップし、私の元のリストの各順列にそれを適用する関数を記述します。私はこれらのサブグループの並べ替えをループし、それらのパーティションの長さが同じであれば、重複を識別できるように並べ替えます。私はこれにもっと良いアプローチがあるかどうかはわかりません。

def return_partition(my_list,num_groups): 
    filtered=[] 
    for perm in itertools.permutations(my_list,len(my_list)): 
     for sub_group_perm in subgrups(list(perm)): 
      if len(sub_group_perm)==num_groups: 
       #sort within each partition 
       sort1=[sorted(i) for i in sub_group_perm] 
       #sort by first element of each partition 
       sort2=sorted(sort1, key=lambda t:t[0]) 
       #sort by the number of elements in each partition 
       sort3=sorted(sort2, key=lambda t:len(t)) 
       #if this new sorted set of partitions has not been added, add it 
       if sort3 not in filtered: 
        filtered.append(sort3) 
    return filtered 

私の元のサンプルリストでそれを実行すると、2つのパーティションと3つのパーティションでテストして、望ましい出力が得られることがわかります。

>>> for i in return_partition([1,2,3,4],2): 
...  print i  
... 
[[1], [2, 3, 4]] 
[[4], [1, 2, 3]] 
[[1, 2], [3, 4]] 
[[3], [1, 2, 4]] 
[[1, 3], [2, 4]] 
[[2], [1, 3, 4]] 
[[1, 4], [2, 3]] 
>>> 

>>> for i in return_partition([1,2,3,4],3): 
...  print i   
... 
[[1], [4], [2, 3]] 
[[3], [4], [1, 2]] 
[[1], [2], [3, 4]] 
[[1], [3], [2, 4]] 
[[2], [4], [1, 3]] 
[[2], [3], [1, 4]] 
>>>