Python限定组合

Question

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

例如:

假设 'ABCD' 在 ['A', 'B', 'C', 'D'] 中并且我想要长度为 2 的组合。所有可能的这种情况下的组合为 6 (n!/((n-k)!x k!))。我想得到 0.6 -> 1(四舍五入)的 10%。

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

---

这里有一些关于我的问题的更多信息。

我有

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

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

def all_way(points):
    point = len(points)
    allrout = []
    allrout = list(itertools.permutations(points, point))
    return allrout

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

Answer 1

我们可以使用 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))

输出

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

正如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))