如何在不重复的情况下从笛卡尔积中采样

Question

我有一个集合列表，我希望对 n 个不同的样本进行采样，每个样本都包含每个集合中的一个项目。我不想要的是按顺序排列，因此，例如，我将从第一组中获取所有样本，其中必须包含相同的项目。我也不想创建所有笛卡尔积，因为这在效率方面可能是不可能的......知道如何去做吗？或者甚至可以近似这种行为？

不起作用的示例：

(prod for i, prod in zip(range(n), itertools.product(*list_of_sets)))

Answer 1

上述所有解决方案都浪费了大量资源来过滤迭代结束时的重复结果。这就是为什么我想到了一种从开始到结束都具有（几乎）线性速度的方法。

想法是：（仅在您的脑海中）为标准阶笛卡尔积的每个结果提供一个索引。这将是例如Ax BxC与2000x 1x 2=4000元素：

0: (A[0], B[0], C[0])
1: (A[1], B[0], C[0])
...
1999: (A[1999], B[0], C[0])
2000: (A[0], B[0], C[1])
...
3999: (A[1999], B[0], C[1])
done.

所以还有一些问题没有解决：

• 如何获得可能的索引列表？答案：只需相乘2000*1*2=4000，其下的每个数字都将是有效索引。
• 如何在不重复的情况下按顺序生成随机索引？有两个答案：如果您想要具有已知样本大小的样本n，只需使用random.sample(xrange(numer_of_indices), n). 但是，如果您还不知道样本大小（更一般的情况），则必须动态生成索引以免浪费内存。在这种情况下，你可以生成index = random.randint(0, k - 1)与k = numer_of_indices获得第一指数和k = number_of_indices - n对n日的结果。只需检查下面的代码（请注意，我在那里使用单边链表来存储完成的索引。它使插入操作 O(1) 操作，我们在这里需要大量插入）。
• 如何从索引生成输出？答：好吧，假设我们的索引是i。然后i % 2000将是结果的索引A。现在i // 2000可以递归地处理为剩余因子的笛卡尔积的索引。

所以这是我想出的代码：

def random_order_cartesian_product(*factors):
    amount = functools.reduce(lambda prod, factor: prod * len(factor), factors, 1)
    index_linked_list = [None, None]
    for max_index in reversed(range(amount)):
        index = random.randint(0, max_index)
        index_link = index_linked_list
        while index_link[1] is not None and index_link[1][0] <= index:
            index += 1
            index_link = index_link[1]
        index_link[1] = [index, index_link[1]]
        items = []
        for factor in factors:
            items.append(factor[index % len(factor)])
            index //= len(factor)
        yield items

Answer 2

sample您可以从库中使用random：

import random
[[random.sample(x,1)[0] for x in list_of_sets] for _ in range(n)]

例如：

list_of_sets = [{1,2,3}, {4,5,6}, {1,4,7}]
n = 3

可能的输出将是：

[[2, 4, 7], [1, 4, 7], [1, 6, 1]]

编辑：

如果我们想避免重复，我们可以使用while循环并将结果收集到set. 此外，您可以检查其n是否有效并返回无效值的笛卡尔积n：

chosen = set()
if 0 < n < reduce(lambda a,b: a*b,[len(x) for x in list_of_sets]):
    while len(chosen) < n:
        chosen.add(tuple([random.sample(x,1)[0] for x in list_of_sets]))
else:
    chosen = itertools.product(*list_of_sets)