0

長さ n>=k>=0 の指定されたリストのサイズ 'k' のすべてのサブセットを検索し、それらのサブセットのリストを返す再帰関数を構築したいと考えています。

例: 入力リストが [1,2,3,4] で k = 2 の場合、関数は [[4,3],[2,4],[2,3],[1,4], [1,3]、[1,2]]

リストの異なる配列は同じリストと見なされることに注意してください。

この種の再帰はうまくいくはずだと思います：

return [lst[0]] + choose_sets(lst[1:],k-1)   ¬¬and¬¬   choose_sets(lst[1:],k)

関数はどこにありますかchoose_sets(lst,k)。

意味：

入力 : [1,2,3,4] 、k=3

呼び出し:

[1] + [2,3,4],k=2 および [2,3,4],k=3

等々...

これらの2つの再帰呼び出しを「同時に」呼び出す方法について、誰かが私を導くことができますか? そして、私の「終了期間」はどうあるべきですか？

ありがとう。

4

2 に答える 2

2

size のリストがあり、 sizenのすべてのサブセットが必要だとしますk。
これは基本的に次と同じです。

リストの各要素に対して、要素を含まない新しいリストを作成し、新しいリスト
でサイズのすべてのサブセットを見つけk-1(これは再帰呼び出しです)、
すべてのリストに remove 要素を追加します。

さて...このソリューションには繰り返しがあります。たとえば、あなたが示した例では、[4、1]と[1、4]の両方が得られます。ただし、結果が重複しないように少し変更できます。


重複を処理する ために編集

def choose_sets(l, k):
  if k == 0:
    return [[]]
  if len(l) == 0:
    return []
  l2 = l[1:]
  subsets = choose_sets(l2, k-1)
  for s in subsets:
    s.append(l[0])
  return subsets+ choose_sets(l2, k)
于 2013-04-25T18:29:27.627 に答える