配列（要素数N）を任意のn個の配列に分割する方法

前提

配列（要素数N,文字列）を任意のn個の配列に分割する方法アルゴリズムをご教示頂きたいです。
分割する全パターンを列挙したいと考えております。
各パターン内の要素は順不同です。（ex.[1,2,3]=[2,3,1]）

汎用的な実現方法を提示していだだけると幸いです。
もしくは、アルゴリズムの名称でも構いません。
よろしくお願いいたします。

実現したいこと

入力配列
[1,2,3,4,5]

出力結果
(n=1)
[[1,2,3,4,5]]

(n=2)
[{[1][2,3,4,5]},{[1,2][3,4,5]},{[1,2,3][4,5]},{[1,2,3,4][5]}]
[{[2][1,3,4,5]},{[2,3][1,4,5]},...]

(n=3)
[{[1][2][3,4,5]},{[1,2][3][4,5]},...]
...

...

(n=5)
[{[1]},{[2]},{[3]},{[4]},{[5]}]

m.ts10806

2022/09/21 04:59

言語限らないなら言語タグを乱雑につけるより「アルゴリズム」系のタグをつけられたほうが良いと思います。

saww121

2022/09/21 05:01

承知いたしました。ご助言いただきありがとうございます。

m.ts10806

2022/09/21 05:01

質問は編集できますので適宜ご対応を。

saww121

2022/09/21 05:05

タグを修正しました。

退会済みユーザー

2022/09/21 05:18

要素に同じ値が含まれるケースは想定しますか。想定する場合、同じ数字でも区別して別カウントしますか? また、要素数Nや分割数nはどの程度まで想定していますか?

saww121

2022/09/21 05:20

要素に同じ値は含まれません。要素数N,分割数nともに最大100程度を想定しています。

行動規範の内容に同意します

回答2件

ベストアンサー

再帰的にやっていくのが、わかりやすい方法ではあります。

まず、再帰を止めるパターンとして、

1分割は1通り
個数と同じだけの分割も1通り

があって、どちらにも当てはまらない場合は以下の2通りが考えられます。

先頭1個だけ1グループにして、残りをn-1分割
先頭以外をn分割して、先頭1個はn個あるグループのどれかに入れる

投稿2022/09/21 05:38

maisumakun

総合スコア145183

saww121

2022/09/21 06:32

ありがとうございます。再帰は苦手ですがトライしてみます。

行動規範の内容に同意します

配列を分割した後の並びが変わらないもののみを列挙するという条件であれば、以下のような考えで実現できます。

配列を分割するn-1本の棒をどこに挿入すればよいかという問題として考えればよいと思います。
棒の位置はN-1個からn-1個を選ぶ組み合わせで求めることができます。
Pythonではitertools.combinationsという関数があるのでそれが利用できます。
あとは先頭から棒の位置に従って配列を分割すればよいです。
Pythonではlst[start:end]というスライス表記で簡単にできます。

Python
1import itertools
2
3def split(lst, n):
4    N = len(lst)
5    ret = []
6    for ps in itertools.combinations(range(1,N), n-1):
7        ps = [0] + list(ps) + [N] # コード単純化のため先頭と末尾の位置も加える
8        ret.append( [lst[s:e] for s,e in zip(ps, ps[1:])])
9    return ret
10
11lst = [1,2,3,4,5]
12
13for i in range(5):
14    ret = split(lst, i+1)
15    print(f'{i+1} {ret}')
16
17"""
181 [[[1, 2, 3, 4, 5]]]
192 [[[1], [2, 3, 4, 5]], [[1, 2], [3, 4, 5]], [[1, 2, 3], [4, 5]], [[1, 2, 3, 4], [5]]]
203 [[[1], [2], [3, 4, 5]], [[1], [2, 3], [4, 5]], [[1], [2, 3, 4], [5]], [[1, 2], [3], [4, 5]], [[1, 2], [3, 4], [5]], [[1, 2, 3], [4], [5]]]
214 [[[1], [2], [3], [4, 5]], [[1], [2], [3, 4], [5]], [[1], [2, 3], [4], [5]], [[1, 2], [3], [4], [5]]]
225 [[[1], [2], [3], [4], [5]]]
23"""