创造了许多限，随机排列的名单
https://stackoverflow.com/questions/93353
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我需要一个随机的清单排列。元素可以是任何东西，但假定它们是整数0通过x-1。我想让y名单，每个含有z元素。规则是，没有列出可能包含相同的元件的两次和在所有列出的次数每个元素是用的是相同的(或尽可能接近).例如，如果我的元素分别为0、1、2、3、y6和z的是2,然后，一个可能的解决方法是：
0,3 1,2 3,0 2,1 0,1 2,3
每一行仅仅具有独特要素，并没有要素已使用超过3次。如果y7，然后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)
其他提示
好的，一方式近似于：
1-洗你的清单
2-采取y第一个元素形成的下一行
4-重复(2)只要你有的数字列表中的
5-如果你没有足够的数字完成列表中，改组的原始清单，并采取所缺少的元素，使得确保你不要夺回数字。
6-开始在步骤(2)只要你需要排
我认为这应该是随机的，你可以把它将用于确保按照你的准则。另外，你必须非常小的考验为重复的要素。
第一，你可以随时随机排列的结束，因此，让我们不用担心制作的"随机排列"(硬);只是担心1)使排列(简单)和2)他们随机(简单).
如果你想要"真正的"随机的团体，你不得不接受随机自然并不真正允许约束的"分配"的结果--你可以得到或可能得到一个运行的类似的。如果你真的想即使分发，第一个使该组均匀分布，然后随机挑选他们作为一个群体。
你必须使用每个元件的设置x均匀?这是不明确的规则，我不仅作如下解释：
注意以下几点："在所有列出的次数每个元素是用的是相同的(或尽可能接近)"
基于这种标准和规则，z < x*我假设你可以简单地列举的所有项目上的所有名单。所以你就自动使y清单的项目列举的位置z。你的例子不能满足上述规则尽我的版本。用你的例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和仍然履行的规则，该规则没有列出可能包含相同的元件的两倍。因此，这个规则要求z不能超过x。
根据新的细节的意见，了解可能只是执行标准的随机排列代算法。有一个长时间的讨论的随机排列代算法在这里：
http://www.techuser.net/randpermgen.html
(从Google搜索：随机排列的产生)
这一工作在红宝石：
# 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
