2

この質問は、おそらく次の2つの質問の組み合わせですが、視点が少し異なります。

サブコンビネーションを生み出す

制限付きのサブコンビネーションを生成します

最初の質問のコードを要件に合わせて調整しました。

def sub_combinations(segment):
    for i in range(1, len(segment)):
            for j in sub_combinations(segment[i:]):
                    yield [segment[:i]] + j 
    yield [segment]

max = 4

for p in sub_combinations([1, 2, 3, 4, 5, 6, 7]):
    if len(p) == max:
        print map(list, p)

これにより、次のように出力されます。

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

ここで問題となるのは、サイズの大きいリストの場合、これには時間がかかりすぎることです。これを実装するためのより効率的/pythonicな方法はありますか？関数自体に引数「max」を組み込むにはどうすればよいですか？多くの方法を試しましたが、再帰関数を操作するのに苦労しました。

4

1 に答える 1

4

希望する結果は、リストを（たとえば）4つの空でないサブリストに分割するすべての方法として説明できるようです。これは、分割位置のすべての可能な組み合わせを生成することによって行うことができます。

def split_sequence(seq, chunks):
    for splits in itertools.combinations(range(1, len(seq)), chunks - 1):
        left = (None,) + splits
        right = splits + (None,)
        yield [seq[l:r] for l, r in zip(left, right)]

出力例：

>>> list(split_sequence(range(7), 4))
[[[0], [1], [2], [3, 4, 5, 6]],
 [[0], [1], [2, 3], [4, 5, 6]],
 [[0], [1], [2, 3, 4], [5, 6]],
 [[0], [1], [2, 3, 4, 5], [6]],
 [[0], [1, 2], [3], [4, 5, 6]],
 [[0], [1, 2], [3, 4], [5, 6]],
 [[0], [1, 2], [3, 4, 5], [6]],
 [[0], [1, 2, 3], [4], [5, 6]],
 [[0], [1, 2, 3], [4, 5], [6]],
 [[0], [1, 2, 3, 4], [5], [6]],
 [[0, 1], [2], [3], [4, 5, 6]],
 [[0, 1], [2], [3, 4], [5, 6]],
 [[0, 1], [2], [3, 4, 5], [6]],
 [[0, 1], [2, 3], [4], [5, 6]],
 [[0, 1], [2, 3], [4, 5], [6]],
 [[0, 1], [2, 3, 4], [5], [6]],
 [[0, 1, 2], [3], [4], [5, 6]],
 [[0, 1, 2], [3], [4, 5], [6]],
 [[0, 1, 2], [3, 4], [5], [6]],
 [[0, 1, 2, 3], [4], [5], [6]]]
于 2012-07-02T12:01:29.873 に答える