5

私はpythondocsから例をコピーしています。

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

powerset結果が遅延評価されたままである間に、取得する値の順序をどのようにランダム化できますか？

編集：私がそれを望む理由は、派生したセットの合計を計算し、同じ合計を持つ2つのセットを見つけたらすぐに停止したいからです。私が間違っていなければ、問題はNP完全です。

4

4 に答える 4

2

itertools.combinations()入力から設定された順序で結果が得られます。これを前提として、入力リストをシャッフルして要素のランダムな順序を生成できます（明らかに、結果の可能な順序ははるかに少なくなります）。

def random_powerset(iterable):
     s = list(iterable)
     lengths = list(range(len(s)+1))
     shuffle(lengths)
     return chain.from_iterable(combinations(s, r) for r in lengths if not shuffle(s))

shuffle(s)（これは少し醜いハックです。常に返されることがわかっているFalseので、の呼び出しごとに確実に実行されるように条件として追加できますcombinations()。）

長さのリストを事前に生成して、それもシャッフルできるようにします。

完全にランダムではありません（順序は引き続き存在します。たとえば、長さnのすべての要素がクラスター化され、これらの要素は入力のランダムな順序に応じた順序になります）が、かなりの量があります。それがあなたにとって十分であるならば、ランダム性の。

出力例：

>>> list(random_powerset(range(3)))
[(), (2,), (0,), (1,), (2, 1), (2, 0), (1, 0), (1, 2, 0)]
>>> list(random_powerset(range(3)))
[(), (0, 1), (0, 2), (1, 2), (0, 1, 2), (2,), (0,), (1,)]
>>> list(random_powerset(range(3)))
[(0, 1, 2), (2,), (1,), (0,), (0, 2), (0, 1), (2, 1), ()]
>>> list(random_powerset(range(3)))
[(1, 2, 0), (0,), (2,), (1,), (), (0, 1), (0, 2), (1, 2)]
>>> list(random_powerset(range(3)))
[(), (2, 1), (2, 0), (1, 0), (0,), (2,), (1,), (2, 1, 0)]
>>> list(random_powerset(range(3)))
[(1, 0), (1, 2), (0, 2), (0, 2, 1), (), (1,), (0,), (2,)]

それが怠惰にならないようにすることなくできる最善のことだと思います。

于 2012-05-05T20:12:17.493 に答える
2

別のアイデアがあります：組み合わせジェネレーターを保存し、すべてを消費するまでランダムに生成します。これにより、セットサイズの順序もランダム化されます。

編集：要素を合計するので、単一のセット内の要素の順序は気にしないと思います。そうした場合、random.shuffle(next_value)利回りの前に置くことができます。

import itertools
import random

def random_powerset(l):
    combs = [itertools.combinations(l,i) for i in range(len(l)+1)]
    while combs:
        comb_index = random.choice(range(len(combs)))
        try:
            next_value = next(combs[comb_index])
            yield next_value
        except StopIteration:
            combs.pop(comb_index)

出力：

In : list(random_powerset(range(3)))
Out: [(0, 1), (0, 2), (0, 1, 2), (1, 2), (), (0,), (1,), (2,)]

In : list(random_powerset(range(3)))
Out: [(0, 1, 2), (0,), (), (0, 1), (1,), (0, 2), (1, 2), (2,)]

In : list(random_powerset(range(3)))
Out: [(0, 1), (0, 1, 2), (0, 2), (), (0,), (1,), (1, 2), (2,)]

In : list(random_powerset(range(3)))
Out: [(), (0,), (0, 1), (0, 1, 2), (1,), (0, 2), (2,), (1, 2)]

In : list(random_powerset(range(3)))
Out: [(), (0, 1), (0,), (0, 1, 2), (1,), (0, 2), (2,), (1, 2)]

In : list(random_powerset(range(3)))
Out: [(0, 1), (0,), (0, 2), (1, 2), (), (1,), (2,), (0, 1, 2)]

In : list(random_powerset(range(3)))
Out: [(), (0, 1, 2), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2)]
于 2012-05-05T20:56:43.230 に答える
2

これは怠惰でランダムな解決策です。

import random

def powerset(seq):
    n = 2**len(seq)
    used = set([])
    while len(used) < n:
        choice = random.randint(0, n - 1)
        if not (choice in used):
            used.add(choice)
            binary = bin(choice)[2:].zfill(len(seq))
            yield [i[1] for i in zip(binary, seq) if i[0] == '1']
            #or following line if > python 2.7:
            #yield itertools.compress(seq, binary)

print list(powerset([1,2,3]))
print list(powerset([1,2,3]))
#output:
[[3], [1], [2, 3], [], [1, 2], [2], [1, 3], [1, 2, 3]]
[[2, 3], [1, 3], [1], [1, 2, 3], [1, 2], [2], [3], []]

[1, 2, 3]バイナリでの組み合わせを検討する場合：

n  123 

0  000
1  001
2  010
3  011
4  100
5  101
6  110
7  111

各組み合わせには、一意のバイナリ識別子でラベルを付けることができます。そして、常に2**len(seq)組み合わせがあります....だから：

  1. 0、、、およびの間の整数をランダムに選択します2**len(seq) - 1。
  2. 以前に使用したことがないことを確認します（使用した場合は、もう一度描画します）。
  3. バイナリに変換します。
  4. で圧縮しseqます。
  5. zip形式の2進数の場合は'0'、出力から除外します。

これは怠惰で、大規模な場合に機能しseqます。

小さな警告：

問題がある可能性がありますが、それはおそらくあなたにとって重要ではありません。シーケンスの終わりに向かって、再描画を繰り返すと問題が発生する可能性があります（これには時間がかかる可能性があります）。すでに抽選された番号を抽選する確率はnumber of successful draws / 2**len(seq)、であるため、特定の抽選でg、未使用の新しい番号を見つけるために予想される抽選数は次のようになります。

n / (n - g)
#where n = 2**len(seq)

n小さい場合、または大きい場合は、どちらでもかまいませnんg << n（これらの状況のいずれかまたは両方が発生する可能性が非常に高いため、どちらも大きな問題にはなりません）。実際、大きい場合は、最初の反復がに近づくまでの予想される反復回数として、繰り返しをn省略してチェックすることができます。usedn**0.5

于 2012-05-07T11:46:07.760 に答える
1

あなたが超えれば、Lattywareのソリューションをいくらか改善することが可能ですitertools.chain：

def chain_random(iterables):
    iterables = list(iterables)
    icount = len(iterables)
    if icount == 0: return 
    while icount > 1:
        shuffle(iterables)
        try:
            yield iterables[-1].next()
        except StopIteration:
            iterables.pop()
            icount -= 1
    for element in iterables[0]:
        yield element

def random_powerset(iterable):
    s = list(iterable)
    lengths = list(range(len(s)+1))
    shuffle(lengths)
    return chain_random(combinations(s, r) for r in lengths if not shuffle(s))

出力例：

>>> list(random_powerset(range(3)))
[(), (2, 1, 0), (1, 0), (1, 2), (2,), (0, 2), (1,), (0,)]
>>> list(random_powerset(range(3)))
[(1, 0), (1, 2), (0, 2, 1), (2,), (), (0, 2), (0,), (1,)]
>>> list(random_powerset(range(3)))
[(0, 1), (), (0, 2), (0,), (1, 2), (2, 0, 1), (1,), (2,)]
>>> list(random_powerset(range(3)))
[(), (1, 2), (2,), (1, 0), (0,), (2, 0), (1,), (1, 0, 2)]
>>> list(random_powerset(range(3)))
[(0, 1), (), (2,), (0, 2), (1, 2), (1,), (1, 2, 0), (0,)]
>>> list(random_powerset(range(3)))
[(0, 2, 1), (0,), (), (2, 0), (1,), (2, 1), (2,), (0, 1)]

itertoolsはCで書かれているので、chain_randomより遅くなりitertools.chainます。しかし、この方法でより多くのランダム化が得られます。

于 2012-05-05T21:02:28.443 に答える