在执行变量嵌套循环以进行置换之前应用条件

Question

我需要通过以下方式获得排列：我有N插槽，这个插槽可以填充从1 to D. 为了得到所有可能的排列，我写了一个循环，它给了我每一种不同的可能性。这些循环看起来有点“奇怪”，因为它是一个需要可变的嵌套循环。这个循环需要两天时间才能完成（对于我的 N = 8 和 D = 25 的条件），但是我只需要槽中变量之和等于 的排列"D"。import numpy as npfrom tqdm import tqdmN = 4 # actualy 8D = 16  # actually 25test = np.ones(shape=N)for k in range(0,pow(D-1,N)):    if sum(test) == D:        print("this is a suiting fit!",test)    # last one gets always changed    if test[N-1]+1 < D:        test[N-1] += 1    else:        test[N-1] = 1        for idx in range(2,len(test)+1):            if test[len(test) -idx] + 1 < D:                test[len(test) - idx] += 1                break            else:                test[len(test) - idx] = 1由于上面的循环可能看起来有点混乱，我将它加入了嵌套循环for i in range(0,D-1):    for j in range(0,D-1):        for k in range(0,D-1):            for l in range(0,D-1):                if k+1+l+1+j+1+i+1 == D:                    print("this is a suting fit!",k+1,l+1,j+1,i+1)我不知道如何通过简化或在遍历排列之前应用条件来使其更快，感谢任何帮助

Answer 1

我可能没有完全理解这个问题，但是，如果我理解了，这种完全不同的方法可以在几秒钟内解决N=8,实例。D=25

>>> sum(1 for x in gensums(4, 16))

455

似乎与您的代码返回的内容相匹配，并且

>>> sum(1 for x in gensums(8, 25))

346104

上次运行的示例x：

[9, 2, 3, 1, 1, 1, 1, 7]

这在尝试扩展部分解决方案的过程中使用递归来应用约束，因此可以提前切断许多无结果的路径。

注意：为了提高效率，它产生的列表通常是同一个列表对象，所以如果你想保存结果供以后使用，一定要复制每个结果。

编辑：替换为更快的版本，也许更清晰一些。

编辑：还有一个改进：添加nslots == 1允许断言的情况remaining并且nslots在函数入口处都是非零的。

def gensums(N, D):

    def inner(sofar, nslots, remaining):

        assert remaining and nslots

        # If only 1 slot left, it's forced.

        if nslots == 1:

            sofar.append(remaining)

            yield sofar

            sofar.pop()

            return

        # If num slots equal to remaining, they must all be 1.

        if nslots == remaining:

            yield sofar + [1] * remaining

            return

        # What can we add next?

        # What's left over must be enough to put at least 1 into

        # each slot, so must have:

        #     remaining - candidate >= nslots - 1, or

        #     candidate <= remaining - nslots + 1

        sofar.append(None)

        for candidate in range(1, remaining - nslots + 2):

            sofar[-1] = candidate

            yield from inner(sofar, nslots - 1,

                             remaining - candidate)

        sofar.pop()

    return inner([], N, D)

Answer 2

您可以使用排列并给出长度。

from itertools import permutations

d = 16  

n = 4

for item in permutations(range(d), r=n):

    if sum(item) == d:

        print("this is a suiting fit!", item)

我想你可能不需要排列

from itertools import product

d = 16  

n = 4

for item in product(range(d), repeat=n):

    if sum(item) == d:

        print("this is a suiting fit!", item)