Python有限组合

Question

我有一个有200个元素的列表。我想随机计算这些元素的所有长度组合的10%，并将结果存储在一个列表中。在

例如：

假设'ABCD'如['A', 'B', 'C', 'D']中所示，我想要长度为2的组合。在这种情况下，所有可能的组合都是6（n！/（n-k）！x k！））。我想要10%的0.6->；1（四舍五入）。在

我试过itertools.combinations('ABCD', 2)，但它给了我所有的组合。在

---

以下是关于我的问题的更多信息。在

我有

all_points_coordinates =  [
    [-1.6339171050450814, 2.5160117038362722], 
    [-1.7207293090531386, 2.4574561328669748], 
    [0.10469849010750323, 2.9981724810572872],
]

我想计算其中3个的组合并使用

^{pr2}$

但它给了我我所有观点的组合。当我运行它100点，这是非常耗时的，所以我只想计算这些组合的有限数量。在

Answer 1

如果您不想在拾取一小部分组合之前预先计算所有组合，则有两个选项：

1. 很难看，但做得很好

   • 重新排列列表中的元素。将结果添加到集合
   • 继续，直到集合达到所需长度。在

2. 美丽而复杂

   • 创建索引列表<；n！（其中n是列表中的元素数）
   • 计算每个索引的组合（类似于this question）。在

Answer 2

另一个相当简单的可能性：生成所有的组合，但只保留那些随机变量为< 0.1的组合，以获得（大约）10%的结果组合。在

>>> sum(1 for _ in itertools.combinations(range(100), 3)) # total count for comparison
161700
>>> res = [c for c in itertools.combinations(range(100), 3) if random.random() < 0.1]
>>> len(res)
16227

与使用random.sample相比，它的优点是不需要将所有的组合都保存在内存中，尽管它仍然会生成所有的组合，但会立即丢弃其中的90%。此外，结果将只有大致10%的组合，但不完全是。不过，对于数量庞大的人来说，这应该不是什么大问题。在

Answer 3

我们可以使用random.sample生成随机组合，并使用一个集合来确保不会多次生成任何组合。下面是一个简单的演示。在

from random import seed, sample

seed(42)

def random_combinations(seq, size, num):
    combos = set()
    while len(combos) < num:
        item = sample(seq, size)
        combos.add(tuple(item))
    return list(combos)

# test

data = [
    (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), 
    (10, 11), (12, 13), (14, 15), (16, 17), (18, 19),
]

# Make 20 random 3-element combinations
combos = random_combinations(data, 3, 20)
for i, item in enumerate(combos, 1):
    print('{:>2}: {}'.format(i, item))

输出

^{pr2}$

正如tobias_k在评论中提到的，这段代码只适用于num不太接近组合总数的情况。如果您想要<；50%的组合，应该没问题，但除此之外，它很有可能重新生成已经生成的组合，这将导致它长时间循环。在

---

注意，这段代码认为((2, 3), (12, 13), (8, 9))不同于以不同顺序包含这3对的元组，例如((2, 3), (8, 9), (12, 13))。在

如果你不想的话，我们可以把我们的东西做成一套。我们需要为此使用frozenset，因为正规集是可变的，因此不易损坏，因此不能设置项。在

from random import seed, sample

seed(42)

def random_combinations(seq, size, num):
    combos = set()
    while len(combos) < num:
        item = sample(seq, size)
        combos.add(frozenset(item))
    return [tuple(u) for u in combos]

# test

data = [
    (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), 
    (10, 11), (12, 13), (14, 15), (16, 17), (18, 19),
]

# Make 20 random 3-element combinations
combos = random_combinations(data, 3, 20)
for i, item in enumerate(combos, 1):
    print('{:>2}: {}'.format(i, item))

输出

 1: ((0, 1), (2, 3), (6, 7))
 2: ((0, 1), (2, 3), (8, 9))
 3: ((16, 17), (6, 7), (0, 1))
 4: ((12, 13), (2, 3), (18, 19))
 5: ((12, 13), (2, 3), (8, 9))
 6: ((12, 13), (18, 19), (0, 1))
 7: ((8, 9), (4, 5), (10, 11))
 8: ((16, 17), (2, 3), (18, 19))
 9: ((8, 9), (6, 7), (14, 15))
10: ((0, 1), (4, 5), (12, 13))
11: ((8, 9), (10, 11), (18, 19))
12: ((10, 11), (6, 7), (2, 3))
13: ((0, 1), (14, 15), (2, 3))
14: ((10, 11), (18, 19), (6, 7))
15: ((8, 9), (2, 3), (6, 7))
16: ((4, 5), (6, 7), (18, 19))
17: ((8, 9), (4, 5), (2, 3))
18: ((16, 17), (4, 5), (6, 7))
19: ((16, 17), (6, 7), (12, 13))
20: ((4, 5), (10, 11), (14, 15))