順列のランダムなリストを作成する必要があります。要素は何でもかまいませんが、0 から x-1 までの整数であると仮定します。それぞれが z 要素を含む y リストを作成したいと思います。ルールは、どのリストにも同じ要素が 2 回含まれてはならず、すべてのリストで、各要素が使用される回数は同じ (または可能な限り近い) というものです。たとえば、要素が 0、1、2、3、y が 6、z が 2 の場合、考えられる解決策の 1 つは次のとおりです。
0,3 1,2 3,0 2,1 0,1 2,3
各行には一意の要素のみがあり、3 回以上使用された要素はありません。y が 7 の場合、2 つの要素が 4 回使用され、残りは 3 回使用されます。
これは改善される可能性がありますが、それは仕事をしているようです（Python）：
import math, random
def get_pool(items, y, z):
slots = y*z
use_each_times = slots/len(items)
exceptions = slots - use_each_times*len(items)
if (use_each_times > y or
exceptions > 0 and use_each_times+1 > y):
raise Exception("Impossible.")
pool = {}
for n in items:
pool[n] = use_each_times
for n in random.sample(items, exceptions):
pool[n] += 1
return pool
def rebalance(ret, pool, z):
max_item = None
max_times = None
for item, times in pool.items():
if times > max_times:
max_item = item
max_times = times
next, times = max_item, max_times
candidates = []
for i in range(len(ret)):
item = ret[i]
if next not in item:
candidates.append( (item, i) )
swap, swap_index = random.choice(candidates)
swapi = []
for i in range(len(swap)):
if swap[i] not in pool:
swapi.append( (swap[i], i) )
which, i = random.choice(swapi)
pool[next] -= 1
pool[swap[i]] = 1
swap[i] = next
ret[swap_index] = swap
def plist(items, y, z):
pool = get_pool(items, y, z)
ret = []
while len(pool.keys()) > 0:
while len(pool.keys()) < z:
rebalance(ret, pool, z)
selections = random.sample(pool.keys(), z)
for i in selections:
pool[i] -= 1
if pool[i] == 0:
del pool[i]
ret.append( selections )
return ret
print plist([0,1,2,3], 6, 2)
これはRubyで機能します。
# list is the elements to be permuted
# y is the number of results desired
# z is the number of elements per result
# equalizer keeps track of who got used how many times
def constrained_permutations list, y, z
list.uniq! # Never trust the user. We want no repetitions.
equalizer = {}
list.each { |element| equalizer[element] = 0 }
results = []
# Do this until we get as many results as desired
while results.size < y
pool = []
puts pool
least_used = equalizer.each_value.min
# Find how used the least used element was
while pool.size < z
# Do this until we have enough elements in this resultset
element = nil
while element.nil?
# If we run out of "least used elements", then we need to increment
# our definition of "least used" by 1 and keep going.
element = list.shuffle.find do |x|
!pool.include?(x) && equalizer[x] == least_used
end
least_used += 1 if element.nil?
end
equalizer[element] += 1
# This element has now been used one more time.
pool << element
end
results << pool
end
return results
end
使用例：
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 0], [1, 3], [2, 5], [6, 0], [2, 5], [3, 6]]
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 5], [6, 3], [0, 2], [1, 6], [5, 4], [3, 0]]
enter code here
コメントの新しい詳細に基づいて、解決策は単に標準のランダム順列生成アルゴリズムの実装である可能性があります。ここでは、ランダム順列生成アルゴリズムについて長い議論があります。
http://www.techuser.net/randpermgen.html
(From Google search: random permutation generation)
わかりました、それを近似する1つの方法：
1 - リストをシャッフルする
2 - 次の行を形成するために y 個の最初の要素を取得します
4 - リストに数字がある限り (2) を繰り返します
5 - リストを完成させるのに十分な数字がない場合は、元のリストを再シャッフルし、不足している要素を取得します。数字を取り直さないようにします。
6 - 行が必要な限り、ステップ (2) からやり直します
これはできる限りランダムにする必要があり、確実に基準に従うと思います。さらに、重複要素のテストはほとんどありません。
まず、最後にいつでもリストをランダムに並べ替えることができるので、「ランダムな順列」を作成することについて心配する必要はありません (難しい)。そして、1) 順列の作成 (簡単) と 2) それらのランダム化 (簡単) について心配するだけです。
「真に」ランダムなグループが必要な場合は、本質的にランダム化では結果の「均一な分布」の制約が実際には許可されないことを受け入れる必要があります。本当に均等に分散させたい場合は、まずセットを均等に分散させてから、それらをグループとしてランダム化します。
セット x の各要素を均等に使用する必要がありますか? 次の解釈をすることができなかったことは、ルールから明らかではありません。
次の点に注意してください: 「すべてのリストで、各要素が使用される回数は同じ (またはできるだけ近い)」
この基準と z < x* というルールに基づいて、すべてのリストのすべてのアイテムを単純に列挙できると仮定します。したがって、位置 z に列挙された項目の y リストを自動的に作成します。あなたの例は、私のバージョンほど厳密には上記のルールを満たしていません。x={0,1,2,3} y=6 および z=2 の例を使用すると、次のようになります。 0,1 0,1 0,1 0,1 0,1 0,1
今は 2 つも 3 つも使用しませんでしたが、すべてを使用する必要があるとは言いませんでした。それらすべてを使用する必要があり、使用に「できるだけ近い」ことを証明できることを気にしない場合は、次のように、リストを介してすべてのアイテムを列挙するだけです: 0,1 2 ,3 0,1 2,3 0,1 2,3
最後に、本当にすべての要素を使用する必要があるとします。各要素が何回繰り返されるかを計算するには、(y*z)/(x の数) を取ります。そうすれば、リスト内の項目をどのように分割するかについて頭を悩ませる必要がなくなります。余りがある場合、または結果が 1 未満の場合、正確な繰り返し回数が得られないことがわかっているため、そのような場合、計算エネルギーを浪費して完全にすることはあまり重要ではありません。最速の結果は、上記のように列挙することであり、ここでの計算を使用して、完全な結果が達成された理由または達成されなかった理由を示すことであると私は主張します. この計算から、重複するポジションの数を抽出するための凝ったアルゴリズムを実現できますが、「余白に収めるには長すぎます」。
*各リストには同じ z 数の要素があるため、z が x より大きいリストを作成することは不可能であり、リストに同じ要素を 2 回含めることはできないという規則を満たします。したがって、この規則では、z を x より大きくすることはできません。