0

問題

さまざまなタイプの N 個のアイテムが、タイプごとに決定される独自のバケットに均等に分散されています。次のような新しいリストを作成したい:

  1. 各バケットからランダムに選択
  2. 同じバケットから 2 回続けてピックしない
  3. 各バケットは、（可能であれば）最終的なリストに等しい量の表現を持たなければなりません
  4. 言語固有のライブラリを使用しない (別の言語で簡単に実装できない)

例

4 つの異なるタイプの 12 のアイテムがあります。つまり、4 つのバケットがあります。

Bucket A - [a, a, a]
Bucket B - [b, b, b]
Bucket C - [c, c, c]
Bucket D - [d, d, d]

私が欲しいもの

1 から N の間のサイズで繰り返される文字のない、ランダムに分布した上記の項目のリスト。

12 Items: a, d, c, a, b, a, c, d, c, b, d, b

8 Items: c, a, d, a, b, d, c, b

4 Items: c, b, d, a

3 Items: b, c, a (Skipping D)

次のバケットが以前に使用されたバケットと等しくなくなるまでランダムな整数を生成する while ループでこれを実行しようとしていましたが、それは非効率的であり、他の誰かがこの問題を解決するためのより良いアルゴリズムを持っていることを望んでいました.

4

2 に答える 2

1

バケットのランダムなリストを生成し、そこから順番にランダムに選択して、リストからバケットを削除することができます。リストが空の場合、バケットのランダム リストを再生成し、必要な数の項目を選択するまで繰り返します。

バケツからアイテムを繰り返すことはできますか? では、最初にバケット A から 1 番目の「a」を選択した場合、2 回目はそれを選択できますか? それによって解決策が変わります。

于 2012-06-04T17:39:51.503 に答える
1

各バケットから引き分けが連続してはならないという制約に対応して編集されました。基準を満たさない順列を破棄するのは簡単です。2 つのバケットに同一の「ラベル」がある場合、これは (そのままで) 失敗します。

順列itertoolsを使ったちょっとしたハック:random.sample

import random
import itertools as itr
from math import ceil

def buckets_choice(N,labels):
    items = int(ceil(float(N)/len(labels)))
    b = list(itr.chain(*(labels for _ in xrange(items))))

    while True:
        p = random.sample(b,len(b))
        cond = map( (lambda x,y: x==y), p[1:], p[:1])
        if not sum(cond):  return p[:N]

L = ['a','b','c','d']
for _ in xrange(5):
    print buckets_choice(3,L), buckets_choice(8,L), buckets_choice(12,L)

サンプルを実行すると、次のようになります (明確にするために引用符は削除されています)。

(a, b, d) (b, d, c, a, d, a, b, c) (b, c, d, c, d, a, d, b, a, c, b, a)
(b, a, d) (d, a, c, c, a, b, b, d) (c, b, a, b, a, c, b, d, d, a, d, c)
(b, d, a) (b, c, c, a, b, a, d, d) (a, d, a, d, c, b, d, c, a, b, c, b)
(d, c, b) (c, d, a, b, c, b, a, d) (c, b, a, a, b, c, d, c, b, a, d, d)
(b, d, a) (c, b, b, d, c, a, d, a) (c, b, d, a, d, b, b, d, c, a, a, c)
于 2012-06-04T18:23:41.237 に答える