Python中具有边界条件的数组的所有可能组合？

Question

我有一个包含4项的列表，我想找到给定数组长度下这4项的所有可能组合。如果我指定长度为16，我希望使用原始列表中的元素生成16项的所有可能组合

我也有一些限制，所以我希望原始列表中的每个元素在生成的组合中出现一定次数

例如：colors = np.array(["red","blue", "green", "neon green"])

我想生成所有可能的16元素数组，它们以一定的比例使用这些给定的颜色：“红色”必须出现4次，“蓝色”必须出现4次，“绿色”+“霓虹绿”一起出现8次（如果我们有8个绿色，0个霓虹灯绿色，或者反之亦然，或者两者的混合，只要组合中两者的总和是8，这并不重要

我尝试使用itertools.product生成所有可能的组合，然后循环遍历每个组合，以查看它是否符合我的“有效数组”标准，但对于16个元素长的组合，它会超时（尽管如果我要进行4或8个元素长的组合，此方法确实有效）

这是我当前的代码：

def validCombinations(rows, columns):
    possibleCombinations = product(colors,repeat=rows) #generates all the possible combinations
    possibleCombos = [] #possible combinations that match our 1:2:1 ratio restriction
    

    counter = 1

    #loops through each combination and puts each ion in that combination into an array (array a)
    for c in product(possibleCombinations,repeat=columns):
        a = []
        for i in c:
            for j in i:
                a.append(j)


        #if a (the combination) contains a 1:2:1 ratio, then add it to the array of possible combos 
        if a.count("red") == (rows *columns)/4 and a.count("blue") == (rows *columns)/4 and (a.count("green") + a.count("neon green")) == (rows*columns)/2:
              possibleCombos.append(a)

  
    
    print(len(possibleCombos))
    return(possibleCombos)

validCombinations(2,2) #for a list of 4 elements
#validCombinations(4,4) #for a list of 16 elements
#validCombinations(2,4) etc..

itertools.product（）是正确的方法，还是有更快的替代方法

Answer 1

正如Alexander Wu所说，您可能需要重新考虑您的问题定义。 使用itertools.product很可能是接近目标的最佳方式，但是 当前的代码引入了低效率，导致相对较小的代码运行时间过长

但是，如果您尝试使用有效的组合，下面的代码将生成 更有效的是：

import itertools

colors1 = ('blue', 'red')
colors2 = ('green', 'neon green')

def equalCount(c1, sz, curr):
    """ Even representation of c1 in curr. """
    return not all(curr.count(c) == sz for c in c1)

def validCombinations1(c1, c2, size):
    """ List valid combinations of colors."""
    sz = int(size / 2)
    col_iter1 = itertools.filterfalse(lambda x: equalCount(c1, sz/2, x),
                  itertools.product(c1, repeat=sz))
    col_iter2 = itertools.product(c2, repeat=sz)
    vc = tuple(itertools.product(col_iter1, col_iter2))
    return tuple(v[0]+v[1] for v in vc)

vc1 = validCombinations1(colors1, colors2, 4)
print(vc1)
print(len(vc1))
vc2 = validCombinations1(colors1, colors2, 8)
print(len(vc2))
vc3 = validCombinations1(colors1, colors2, 16)
print(len(vc3))

输出：

# (('blue', 'red', 'green', 'green'),
#  ('blue', 'red', 'green', 'neon green'),
#  ('blue', 'red', 'neon green', 'green'),
#  ('blue', 'red', 'neon green', 'neon green'),
#  ('red', 'blue', 'green', 'green'),
#  ('red', 'blue', 'green', 'neon green'),
#  ('red', 'blue', 'neon green', 'green'),
#  ('red', 'blue', 'neon green', 'neon green'))
# 8
# 48
# 17920

您的代码似乎产生重复排列；请注意，上面的代码 产生一些排列，但没有重复。但是不知道更多 关于“规则”，很难建立一个更合适的程序

我在笔记本电脑上运行了一些计时来比较结果。上面的代码， 相比之下，即使使用置换生成，也需要10微秒 与4号的235微秒相比

%timeit validCombinations(2, 2)
235 µs ± 48.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit validCombinations1(colors1, colors2, 4)
7.93 µs ± 608 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit validPermutations(validCombinations1(colors1, colors2, 4))
10.5 µs ± 1.23 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit validCombinations1(colors1, colors2, 8)
46.4 µs ± 5.58 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit validCombinations1(colors1, colors2, 16)
5.87 ms ± 499 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 2

我认为你试图解决的问题不可行。可能有一种比您当前的方法更快的方法，但即使是理论上最优的解决方案也需要很长时间，除非您有一台运行速度非常快的语言的极快计算机，而且由于您使用的是Python，我认为情况并非如此

您正在搜索四种颜色的所有可能组合。总共有4**16 == 4294967296个组合（每个项目有4个选择，应用产品计数规则），假设生成每个组合需要一毫秒，这将需要1193小时。显然，在Python中迭代所有这些内容是不可行的

即使有更好的方法只生成符合您标准的组合，也仍然是comb(16, 4) * comb(12, 4) * 2**8 == 230630400组合（从16个位置中选择4个位置为红色，从12个位置中选择4个位置为蓝色，那么剩余的8个位置中的每一个都可以是两种颜色中的一种），并且再次假设每个位置都需要一毫秒的时间来处理，那是64小时

你应该考虑改变你的实现，不需要生成每一个组合。也许您只需要检查某个内容是否是有效的组合。或者也许你实际上不需要这么大的数字；如果只输入相对较小的数字，则当前使用的代码不会比最佳值慢太多