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

Question

我需要通过以下方式获得排列：我有N插槽，这个插槽可以填充从1 to D. 为了得到所有可能的排列，我写了一个循环，它给了我每一种不同的可能性。这些循环看起来有点“奇怪”，因为它是一个需要可变的嵌套循环。这个循环需要两天时间才能完成（对于我的 N = 8 和 D = 25 的条件），但是我只需要槽中变量之和等于 的排列"D"。

import numpy as np

from tqdm import tqdm

N = 4 # actualy 8

D = 16  # actually 25

test = 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):&nbsp; &nbsp; def inner(sofar, nslots, remaining):&nbsp; &nbsp; &nbsp; &nbsp; assert remaining and nslots&nbsp; &nbsp; &nbsp; &nbsp; # If only 1 slot left, it's forced.&nbsp; &nbsp; &nbsp; &nbsp; if nslots == 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sofar.append(remaining)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield sofar&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sofar.pop()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; # If num slots equal to remaining, they must all be 1.&nbsp; &nbsp; &nbsp; &nbsp; if nslots == remaining:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield sofar + [1] * remaining&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; # What can we add next?&nbsp; &nbsp; &nbsp; &nbsp; # What's left over must be enough to put at least 1 into&nbsp; &nbsp; &nbsp; &nbsp; # each slot, so must have:&nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; &nbsp; &nbsp;remaining - candidate >= nslots - 1, or&nbsp; &nbsp; &nbsp; &nbsp; #&nbsp; &nbsp; &nbsp;candidate <= remaining - nslots + 1&nbsp; &nbsp; &nbsp; &nbsp; sofar.append(None)&nbsp; &nbsp; &nbsp; &nbsp; for candidate in range(1, remaining - nslots + 2):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sofar[-1] = candidate&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield from inner(sofar, nslots - 1,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;remaining - candidate)&nbsp; &nbsp; &nbsp; &nbsp; sofar.pop()&nbsp; &nbsp; return inner([], N, D)

Answer 2

您可以使用排列并给出长度。from itertools import permutationsd = 16&nbsp;&nbsp;n = 4for item in permutations(range(d), r=n):&nbsp; &nbsp; if sum(item) == d:&nbsp; &nbsp; &nbsp; &nbsp; print("this is a suiting fit!", item)我想你可能不需要排列from itertools import productd = 16&nbsp;&nbsp;n = 4for item in product(range(d), repeat=n):&nbsp; &nbsp; if sum(item) == d:&nbsp; &nbsp; &nbsp; &nbsp; print("this is a suiting fit!", item)