特定のセットの電源セットを計算できるアルゴリズムは何ですか？
https://stackoverflow.com/questions/2779094
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
数字の開始リストに基づいて、数値の組み合わせの一意のリストを効率的に生成したいと思います。
スタートの例 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]組み合わせは必要ありません[1,3,2
解決
あなたが求めていることの名前があります。それはと呼ばれています 電源セット.
「電源セットアルゴリズム」のグーグルでこれを導きました 再帰ソリューション.
Rubyアルゴリズム
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私}）u（{e私} u パワーセット（s- {e私}))
ここでe私 S（シングルトン）の要素です
擬似アルゴリズム
- セットは空になりますか？ done（{}の電源セットは{{}}であることに注意してください）
- そうでない場合は、要素を取り出します
- セットの残りの部分で再帰的にメソッドを呼び出します
- の結合で構成されるセットを返します
- 要素のないセットのパワーセット（再帰呼び出しから）
- この同じセット（つまり、 2.1）しかし、その中にそれぞれの要素が最初に取り出された要素と結合した
他のヒント
数えるだけです 0 に 2^n - 1 カウントのバイナリ表現に従って番号を印刷します。 a 1 その番号とaを印刷することを意味します 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 power(a)
(0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end
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
私のテストでは、RubyではIvladの方法がそれほどうまく機能しません。
OPのコメントから（編集されたコピー）：
この例は、私が実際に行っていることの単純化された形です。数字はプロパティ「数量」を持つオブジェクトです。可能なすべての組み合わせの量を合計してから、量の合計が最も多くのオブジェクトを使用する組み合わせを選択します。
N他のいくつかの境界内にあります、 例えばx < N < y.
あなたが持っているのは最適化の問題です。この最適化問題にアプローチする正しい方法は、列挙問題（これが尋ねたもの）に分解し、ろ過問題（おそらくあなたがやり方を知っている）に分解することです。
まだ気付いていないのは、この種のソリューションが（a）理論分析のために、または（b）の非常に小さな値の場合にのみ機能するということです。 n. 。あなたが求めている列挙は指数関数的です n, 、つまり、実際に走るのに時間がかかりすぎるものになってしまうことを意味します。
したがって、最適化の問題をどのように投げかけるかを把握し、新しい質問を書き、これを指すように編集します。
スキーム内の電力セットを計算するための再帰的および反復ソリューション。ただし、完全にテストされていません
(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（））」」のような表現を試みるとき、「セットオブジェクトは非粉砕できない」と述べました。
多くのプログラミング言語のソリューションも参照してください 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)
