在Python中生成n个组合的最快方法

Question

我有一个包含 10 个元素的数组，正在寻找最快的方法来在 Python 中随机生成 n 个大小为 m 的组合与这 10 个元素。

我必须对所有可能的组合大小（m 从 1 到元素数量）执行此操作，并且 n 也会变化，当可能的组合数量增加时，它也会增加。

For example if my input array is: [a, b, c, d, e, f, g, h, i, j]
for n = 4 and m = 3 the output should be:

(e, b, c)
(i, a, d)
(g, j, e)
(i, f, e)

There can't be twice the same element in one permutation.

我知道 itertool 函数可以生成给定大小的所有组合，但我只需要 n 个组合，而不是全部。所以我不确定使用 itertools 是解决我的问题的最快解决方案（因为我必须在所有生成的组合中随机选择 n 个组合）。

Answer 1

独特元素

对于这种方法，请确保传递的

m

（样本大小）值不大于

array

（总体大小）大小。或者您可以添加 if 语句来检查

m

值。

import random

def generate_combinations(array, m, n):
    """Generate n random combinations of size m"""
    if m > len(array): # Changing the m value to array length if it is greater than length of array
        m = len(array)
    return [random.sample(array, k=m) for _ in range(n)] # for unique element

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 5  # Number of combinations
m = 10

print(generate_combinations(array, m, n))

输出示例

[[8, 1, 2, 5, 4, 3, 6, 7, 10, 9],
 [9, 6, 7, 1, 8, 2, 10, 3, 4, 5],
 [8, 3, 7, 10, 6, 9, 2, 5, 1, 4],
 [10, 8, 9, 2, 6, 5, 7, 4, 1, 3],
 [5, 4, 1, 7, 10, 6, 3, 9, 8, 2]]

---

对于非唯一元素

import random

def generate_combinations(array, m, n):
    """Generate n random combinations of size m using list comprehension"""
    return [random.choices(array, k=m) for _ in range(n)]

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 5  # Number of combinations
m = 10

print(generate_combinations(array, m, n))

输出示例

[[9, 8, 4, 2, 5, 4, 5, 5, 6, 1],
 [2, 6, 10, 3, 6, 1, 7, 6, 2, 4],
 [1, 9, 7, 9, 8, 2, 10, 1, 1, 7],
 [10, 4, 5, 7, 8, 9, 5, 1, 4, 1],
 [9, 3, 3, 5, 9, 4, 9, 8, 10, 6]]

---

或者您可以使用

numpy

（独特）

import numpy as np
def generate_combinations(array, m, n):
    if m> len(array):
        m = len(array)
    return [np.random.choice(array, (1, m), replace=False).tolist()[0] for _ in range(n)]

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 5  # Number of combinations
m = 10

print(generate_combinations(array, m, n))

输出示例

[[6, 7, 9, 10, 8, 4, 1, 2, 3, 5],
 [8, 5, 2, 10, 7, 3, 9, 4, 1, 6],
 [8, 1, 4, 10, 3, 6, 9, 7, 2, 5],
 [7, 4, 8, 5, 3, 9, 6, 10, 1, 2],
 [1, 8, 7, 3, 9, 2, 5, 4, 10, 6]]

Answer 2

对现有答案的评论。

免责声明，正如评论中最初指出的那样，我的先入之见是 codester_09 是最直接的，也可能是最有效的。

首先是错误答案：

• playerJX1：这仅生成前 N 个项目组合，使用

  itertools.combinations

  已经可以使用该组合。
• DarkKnight：这不允许在不同组合中重用相同的项目，这不是预期逻辑的一部分
• Pierre Alex：代码不正确，无法运行（

  combinations

  和

  shuffle

  使用不当）

现在是两个正确答案codester_09和selbie的时间。

我生成了随机输入列表，并将

m

和

n

设置为输入长度的 1/100 和 1/10，然后计算总运行时间并用

perfplot

绘制。

我必须包装 selbie 的

makeRandomPermutation

函数来重复它

n

次：

def selbie(array):
    m = len(array)//100
    n = len(array)//10
    return [makeRandomPermutation(array, m) for _ in range(n)]

获胜者很简单：

[random.sample(array, k=m) for _ in range(n)]

Answer 3

对于一个小列表，这似乎和其他任何东西一样好：

def shuffle(items, m=len(items)):
   for i in range(m):
       j = math.floor(random.random() * len(items))
       items[i],items[j] = items[j],items[i]

def makeRandomPermutations(items, n, m):
   clone = items[0:]
   permutations=[]
   for i in range(n):
       shuffle(clone,m)
       permutations.append(clone[0:m])
   return permutations

示例：

>>> items=['a','b','d','e','f','g','h','i','j']
>>> perms = makeRandomPermutations(items,4,3)
>>> for p in perms:
...      print(p)

['b', 'i', 'j']
['a', 'g', 'e']
['e', 'j', 'a']
['a', 'd', 'h']
>>>

Answer 4

修改这个解决方案，它最初给出时间复杂度为 O(N^2) 的所有组合。这是修改后的版本：

cnt=0
def printCombination(arr, size, m,n):
    global cnt
    data = [0]*m
    combinationUtil(arr, data, 0,
                    size - 1, 0, m,n)
 
def combinationUtil(arr, data, start,
                    end, index, m, n):
    global cnt
    if (index == m):
        for j in range(m):
            print(data[j], end = " ");
        print()
        cnt+=1
        return

    i = start;
    while(i <= end and end - i + 1 >= m - index and cnt<n):
        data[index] = arr[i]
        combinationUtil(arr, data, i + 1,
                        end, index + 1, m, n)
        i += 1
arr = [1, 2, 3, 4, 5]
m = 3
size = len(arr)
n= 5
printCombination(arr, size, m, n)

如果需要，这将打印所有组合，但不是完全随机的（不确定这是否是您想要的）

Answer 5

使用

itertools

由于其高效的实施，将是每个平台上最快的。组合不是预先计算的，而是仅在迭代时计算的。

这样做应该会给你最好的结果：

from itertools import combinations, islice

#: Generates an iterator for 10 elements among all combinations
#: Note that it is not random at all
input_data = [1, 2, 3, 4, 5]
m_size = 3

all_combinations = combinations(input_data, m_size)
subset = islice(all_combinations, 10)


#: To add randomness
from random import shuffle

shuffle(input_data)

all_combinations = combinations(input_data, m_size)
subset = islice(all_combinations, 10)

Answer 6

more-itertools

图书馆可能就是您正在寻找的。

from more_itertools import combination_index, nth_combination
import random
import pprint

digit_set = ['a', 'b', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
no_of_digits = 10
combination_size = 3
last_index = combination_index(digit_set[-1] * combination_size, digit_set * no_of_digits)
random_combinations = [
    nth_combination(digit_set * no_of_digits, combination_size, index)
    for index
    in random.choices(range(last_index), k=10)
]

pprint.pprint(random_combinations, indent=4)

结果：

python rand_combinations.py 
[   ('f', 'h', 'f'),
    ('f', 'a', 'h'),
    ('a', 'j', 'g'),
    ('e', 'j', 'g'),
    ('e', 'd', 'a'),
    ('i', 'g', 'g'),
    ('d', 'd', 'f'),
    ('i', 'd', 'b'),
    ('h', 'f', 'h'),
    ('b', 'd', 'g')]

它会在几秒钟内选择 10,000 个随机组合。