数字の最初のリストに基づいて、数字の組み合わせの一意のリストを効率的に生成したいと思います。
例は開始list = [1,2,3,4,5]しますが、アルゴリズムは次のように機能するはずです[1,2,3...n]
result =
[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]
ノート。重複した組み合わせは必要ありませんが、一緒に暮らすことはできます。たとえば、上記の例では、[1,2,3]として既に存在するため、組み合わせ[1,3,2]は実際には必要ありません。
0カウントして2^n - 1、カウントの2進表現に従って数値を出力するだけです。a1はその番号を印刷することを意味し、印刷し0ないことを意味します。例：
set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
00011 => print {1, 2}
00100 => print {3}
00101 => print {1, 3}
00110 => print {2, 3}
00111 => print {1, 2, 3}
...
11111 => print {1, 2, 3, 4, 5}
あなたが求めているものの名前があります。これはパワーセットと呼ばれます。
「べき集合アルゴリズム」をグーグルで検索すると、この再帰的なソリューションにたどり着きました。
def powerset!(set)
return [set] if set.empty?
p = set.pop
subset = powerset!(set)
subset | subset.map { |x| x | [p] }
end
S =（a、b、c）の場合、べき集合（S）はすべてのサブセットの集合です。 べき集合（S）= {（）、（a）、（b）、（c）、（a、b）、（ a、c）、（b、c）、（a、b、c）}
最初の「トリック」は、再帰的に定義しようとすることです。
停止状態とは何ですか？
S =（）はどのべき集合（S）を持っていますか？
どのようにそれに到達しますか？
セットを1要素減らす
要素を取り出すことを検討してください-上記の例では、{c}を取り出します
S =（a、b）次にべき 集合（S）= {（）、（a）、（b）、（a、b）}
何が欠けている？
べき集合（S）= {（c）、（a、c）、（b、c）、（a、b、c）}
うーん
類似点に気づきましたか？もう一度見てください...
べき集合（S）= {（）、（a）、（b）、（c）、（a、b）、（a、c）、（b、c）、（a、b、c）}
任意の要素を取り出します
べき集合（S）= {（）、（a）、（b）、（c）、（a、b）、（a、c）、（b、c）、（a、b、c）}は
べき集合（S-{c}）= {（）、（a）、（b）、（a、b）}と結合
{c} Uべき集合（S-{c}）= {（c）、（a、c）、（b、c）、（a、b、c）}
べき集合（S）=べき集合（S-{e i }）U（{e i } Uべき集合（S-{e i }））
ここで、e iはS（シングルトン）の要素です。
def power(a)
(0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end
OPによるコメントから（コピー編集）：
この例は、私が実際に行っていることの簡略化された形式です。数値は「数量」というプロパティを持つオブジェクトです。可能なすべての組み合わせの数量を合計してから、数量の合計が他の境界内にあるオブジェクトを最も多く使用する組み合わせを選択し
Nます。x < N < y
あなたが持っているのは最適化問題です。あなたが想定していることは、この最適化問題に取り組む正しい方法は、それを列挙問題（あなたが尋ねたもの）に分解し、次にろ過問題（おそらくあなたはその方法を知っている）に分解することです。
まだ気付いていないのは、この種のソリューションは、（a）理論的分析の場合、または（b）の値が非常に小さい場合にのみ機能するということですn。あなたが求めている列挙は指数関数的です。nつまり、実際に実行するには非常に長い時間がかかることになります。
したがって、最適化問題をそのように提起する方法を理解し、新しい質問を書き、それを指すようにこれを編集します。
hobodaveの答えと同じですが、反復的で高速です（Rubyの場合）。との両方でも機能しArrayますSet。
def Powerset(set)
ret = set.class[set.class[]]
set.each do |s|
deepcopy = ret.map { |x| set.class.new(x) }
deepcopy.map { |r| r << s }
ret = ret + deepcopy
end
return ret
end
私のテストでは、IVladの方法はRubyではあまりうまく機能しません。
スキームで設定されたべき集合を計算するための再帰的で反復的なソリューション。完全にはテストされていません
(define (power_set set)
(cond
((empty? set) (list '()))
(else
(let ((part_res (power_set (cdr set))))
(append (map (lambda (s) (cons (car set) s)) part_res) part_res)))))
(define (power_set_iter set)
(let loop ((res '(())) (s set))
(if (empty? s)
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))
以下は、すでに投稿されているものと同様の再帰的なソリューションです。いくつかのアサーションは、一種の単体テストとして提供されています。セットのセットを表すために「セット」Pythonタイプを使用することはできませんでした。Pythonは、「s.add（set（））」のような式を試してみると、「setオブジェクトはハッシュできない」と言っていました。
http://rosettacode.org/wiki/Power_setで多くのプログラミング言語のソリューションも参照してください。
def generatePowerSet(s, niceSorting = True):
"""Generate power set of a given set.
The given set, as well as, return set of sets, are implemented
as lists.
"niceSorting" optionnaly sorts the powerset by increasing subset size.
"""
import copy
def setCmp(a,b):
"""Compare two sets (implemented as lists) for nice sorting"""
if len(a) < len(b):
return -1
elif len(a) > len(b):
return 1
else:
if len(a) == 0:
return 0
else:
if a < b:
return -1
elif a > b:
return 1
else:
return 0
# Initialize the power set "ps" of set "s" as an empty set
ps = list()
if len(s) == 0:
ps.append(list())
else:
# Generate "psx": the power set of "sx",
# which is "s" without a chosen element "x"
sx = copy.copy(s)
x = sx.pop()
psx = generatePowerSet(sx, False)
# Include "psx" to "ps"
ps.extend(psx)
# Include to "ps" any set, which contains "x"
# Such included sets are obtained by adding "x" to any subset of "sx"
for y in psx:
yx = copy.copy(y)
yx.append(x)
ps.append(yx)
if niceSorting:
ps.sort(cmp=setCmp)
return ps
assert generatePowerSet([]) == [[]]
assert generatePowerSet(['a']) == [[], ['a']]
assert generatePowerSet(['a', 'b']) == [[], ['a'], ['b'], ['a', 'b']]
assert generatePowerSet(['a', 'b','c']) == [[],
['a'], ['b'], ['c'],
['a', 'b'], ['a', 'c'], ['b', 'c'],
['a', 'b', 'c'] ]
assert generatePowerSet(['a', 'b','c'], False) == [ [],
['a'],
['b'],
['a', 'b'],
['c'],
['a', 'c'],
['b', 'c'],
['a', 'b', 'c'] ]
print generatePowerSet(range(4), True)
私の同僚は、ルビーでそれを行うためのエレガントな方法を作成しました。インデックスセットにIVladの概念を使用します。
class Array
def select_by_index(&block)
# selects array element by index property
n = []
each_with_index do |e, i|
if block.call(i)
n << e
end
end
n
end
end
def pow(a)
# power set of a
max = (1 << a.length)
(0...max).map { |i| a.select_by_index { |k| (1 << k) & i != 0 }}
end