0

问题

我有 N 个不同类型的项目均匀地分布到由类型确定的自己的桶中。我想创建一个新列表：

  1. 从每个桶中随机挑选
  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 中选择第一个“a”，您可以第二次选择它吗？那将改变解决方案。

于 2012-06-04T17:39:51.503 回答
1

编辑以响应每个桶中不得连续抽取的约束。丢弃不符合您标准的排列很简单。现在，如果两个桶具有相同的“标签”，这将失败（原样）。

一个小技巧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 回答