Python 有限组合

Question

我有一个包含200个元素的列表。我想要随机计算长度为k的所有组合中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],
]

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

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

但它会给我所有点的组合。当我运行100个点时，这非常耗时，因此我想仅计算其中有限数量的组合。

- Ozan Tunahan Ismailoglu

---

为什么不在找到10%的组合后停止迭代呢？我并没有清楚地看到问题所在...你能进一步阐述吗？ - Tim Pietzcker

前10%？你的问题不是很清楚。 - Willem Van Onsem

itertools.combinations 返回一个迭代器，它不会一次性创建所有的组合。因此，只需循环遍历组合，并在获得足够的组合时退出循环。它们将按顺序排列，而不是随机的。这有关系吗？ - PM 2Ring

itertools.combinations('ABCD', 2)[:(len('ABCD')*percent)] - dsgdfg

@OzanTunahanIsmailoglu，你的列表中可能有重复项吗？ - Ma0

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

- PM 2Ring

---

不错，但你可能需要加上一个警告，不要在num接近总组合数时使用此方法，因为找到最后几个未见过的组合可能需要很长时间。 - tobias_k

但是这是一个集合的工作，我有一个列表，我该如何解决这个问题。我有数据= [[9，-3]，[5，8]，[-6，7]]。 - Ozan Tunahan Ismailoglu

通常最好将坐标对存储为元组而不是列表。有关详细信息，请参见此处。我的代码需要以那种形式输入数据，但转换很容易：newdata = [tuple(u) for u in olddata]。当然，您也可以通过[list(u) for u in newdata]进行反向转换。 - PM 2Ring

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％的组合，而不是完全相同。对于大量数据，这应该不是太大的问题。

- tobias_k

---

不错的方法。希望这能满足原帖作者的需求。我很快会发布使用 sample 的版本。 - PM 2Ring

如果sum需要很长时间，那么组合的总数可以通过解析计算。 - Ma0

@Ev.Kounis 当然可以，只需提供参考号码。实际上获取10%的计算中，我不需要总和。 - tobias_k

Answer 3

如果您不想在挑选少量组合之前预先计算所有组合，则有两个选择：

1. 丑陋但实用

   • 打乱列表的元素。将结果添加到集合中
   • 重复以上步骤直到集合达到所需长度

2. 美观但复杂

   • 创建一个索引列表，其小于 n!（n 是列表中元素的数量）
   • 为每个索引计算组合（类似于 this question）

- Tim Pietzcker

---

我熟悉排列索引，但如何将其应用于组合？ - PM 2Ring

选项1并不能保证不会有重复，是吗？ - Ma0

@Ev.Kounis：是的，它使用了一个集合。这种解决方案的丑陋之处在于，当百分比增加时，它变得非常低效，因为它必须丢弃越来越多的重复项。 - Tim Pietzcker

Answer 4

选项1（非随机，但仅生成所需内容）：

取由itertools.combinations()返回的结果的前10%。

import itertools
from math import factorial, ceil    

original = 'ABCD'
k = 2
percentage = 0.1
configurations = factorial(len(original)) / (factorial(len(original) - k) * factorial(k))
take = ceil(percentage * configurations)
res = []
for i, comb in enumerate(itertools.combinations(original, k), 1):
    res.append(comb)
    if i == take:
        break
print(res, len(res))

---

选项2 (随机选取，但首先生成完整列表):

随机选择由itertools.combinations() 返回的结果中的10%。由于 random.choices()，需要使用Python 3.6。

# Python 3.6 you can do this
import random
import itertools
from math import factorial, ceil

original = 'ABCD'
k = 2
percentage = 0.1
configurations = factorial(len(original)) / (factorial(len(original) - k) * factorial(k))
take = ceil(percentage * configurations)
res = random.choices([x for x in itertools.combinations(original, k)], k=take)

original 也可以是一个列表。

- Ma0

---

但是版本1不是随机的，而版本2需要先生成所有的组合。 - tobias_k

@tobias_k 真的。在答案中添加了注释以使其更清晰。200个元素并不算太多，但OP没有指定组合将包含多少个元素，因此很难估计运行时间。 - Ma0

不清楚原帖作者实际想要什么。我的猜测是，他们想要从他们的200个点列表中随机选择大约20,000对点的10％。但我可能完全错了。;) - PM 2Ring

顺便问一下，你为什么要使用 random.choices？难道不应该使用 random.sample 来做同样的事情吗？ - tobias_k

@tobias_k 唯一的区别是替换。sample 是不带替换的，而 choices 则带有替换。 - Ma0

@Ev.Kounis 啊，对了，我没看到这个。但是，为什么要用choices而不是sample呢？ - tobias_k

Answer 5

我是这样解决我的问题的

point=  len(points)
p=int(point*10/100)
allrout = list(itertools.islice(itertools.permutations(points, point),p ))
print(len(allrout))
return allrout

- Ozan Tunahan Ismailoglu