0

我需要制作一个随机排列列表。元素可以是任何东西,但假定它们是整数 0 到 x-1。我想制作 y 个列表,每个列表都包含 z 个元素。规则是没有列表可以包含两次相同的元素,并且在所有列表中,每个元素的使用次数相同(或尽可能接近)。例如,如果我的元素是 0,1,2,3,y 是 6,z 是 2,那么一种可能的解决方案是:

0,3
1,2
3,0
2,1
0,1
2,3

每行只有唯一的元素,没有元素被使用超过 3 次。如果 y 为 7,则 2 个元素将被使用 4 次,其余 3 次。

4

6 回答 6

2

这可以改进,但它似乎可以完成这项工作(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)
于 2008-09-18T18:12:21.393 回答
0

好的,一种近似的方法:

1 - 随机播放您的列表

2 - 取第 y 个元素形成下一行

4 - 只要列表中有数字,就重复 (2)

5 - 如果您没有足够的数字来完成列表,请重新排列原始列表并取走缺失的元素,确保不要重新取走数字。

6 - 只要您需要行,就从步骤 (2) 重新开始

我认为这应该尽可能随机,并且肯定会遵循您的标准。另外,您对重复元素的测试很少。

于 2008-09-18T15:14:54.173 回答
0

首先,你总是可以在最后对列表进行随机排序,所以我们不用担心做出“随机排列”(困难);并且只需担心 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)/(count of x)。这样,我就不必坐下来担心如何划分列表中的项目。如果有余数,或者结果小于 1,那么我知道我不会得到准确的重复次数,所以在这些情况下,尝试浪费计算能量来使其完美并不重要。我认为最快的结果仍然是像上面那样枚举,并使用这里的计算来说明为什么达到或没有达到完美的结果。可以实现从该计算中提取多少位置将被重复的奇特算法,但是“它太长了,无法容纳在边距中”。

*每个列表具有相同的 z 数量的元素,因此不可能创建 z 大于 x 的列表并且仍然满足任何列表不能包含相同元素两次的规则。因此,该规则要求 z 不能大于 x。

于 2008-09-18T15:20:09.323 回答
0

根据评论中的新细节,该解决方案可能只是标准随机排列生成算法的实现。这里对随机排列生成算法进行了冗长的讨论:

http://www.techuser.net/randpermgen.html

(来自谷歌搜索:随机排列生成)

于 2008-09-18T16:22:11.983 回答
0

这适用于 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
于 2009-12-17T18:48:10.107 回答
0

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

于 2010-05-02T00:45:29.043 回答