python - 来自 N 个非连续重复的 M 个元素的组合

Question

我有以下问题，可以总结如下:

Imagine you have two integers greater than 0, N (which defines the array n=np.array(range(N)) and M. We'd like to generate all the possible combinations of elements of n with length M, with the condition that no equal elements are consecutive.

例如，对于 N=3 (n=[0,1,2]) 和 M=3，我们应该得到:

(0,1,0), (0,1,2) (0,2,0), (0,2,1), (1,0,1), (1,0,2), (1,2,0), (1,2,1), (2,0,1), (2,0,2), (2,1,0), (2,1,2)

即 (0,0,1), (1,1,1), (2,1,1)...等组合，不必出现.请注意，所有有效组合的数量仅由 N*(N-1)**(M-1) 给出。

到目前为止，对于这样的例子，我正在使用这个简单的脚本(它还计算从 m=1 到 m=M 的所有不同长度的组合):

import numpy as np
N = 3
M = 3
p = np.array(range(N))  

ic = [0]*M
c2 = np.zeros((int(N*(N-1)**(M-1)),M))
c1 = np.zeros((int(N*(N-1)**(M-2)),M-1))
c0 = np.zeros((int(N*(N-1)**(M-3)),M-2))
for i in p:
    c0[ic[0],:] = [i]
    ic[0] += 1
    for j in p[p!=i]:
        c1[ic[1],:] = [i,j]
        ic[1] += 1
        for k in p[p!=j]:
            c2[ic[2],:] = [i,j,k]
            ic[2] += 1

问题是这只适用于 M=3 的特定情况，M 可以是任何大于 0 的整数。因此对于某些 M，之前的代码应该有 M 个嵌套循环，必须手动引入。

我试过定义一个循环次数可变的递归函数，比如这个计算组合的数(上面等式给出的数字)的函数:

def rec_f(c,N,M):   
    if n>=1:
        for x in range(N):             
            c=rec_f(c,N,M-1)
    else:
        c += 1            
    return c

我什至不知道为什么它适用于那个简单的问题。现在，问题是我需要知道先前循环的索引才能复制生成所有可能组合的脚本，但我不知道该怎么做。

我还尝试制作一个独特的 for 循环(将迭代 N*(N-1)^(M-1) 次)，请记住组合可以表示为作为以 N 为底的数字，但玩了一段时间后我没有得到任何有用的东西。

如有任何帮助，我将不胜感激，在此先致谢(抱歉发了这么长的帖子)!

Answer 1

只需将最后一个元素(如果有的话)作为可选参数添加到您的递归函数中。此外，不需要 N 参数，只需传递要选择的元素(也使其更普遍适用)。此外，我建议将其作为生成器函数，因为组合的数量可能会变得相当大，因此您可以在它们出现时一个一个地使用它们。

def combinations(elements, m, last=-1):
    if m:
        for x in elements:
            if x != last:
                for rest in combinations(elements, m-1, x):
                    yield (x,) + rest
    else:
        yield ()

或者更紧凑一点，使用 yield from 生成器表达式:

def combinations(elements, m, last=-1):
    if m:
        yield from ((x,) + rest for x in elements if x != last
                                for rest in combinations(elements, m-1, x))
    else:
        yield ()

两个版本的示例结果:

print(*combinations(range(3), 3))
# (0, 1, 0), (0, 1, 2), (0, 2, 0), (0, 2, 1), (1, 0, 1), (1, 0, 2), (1, 2, 0), (1, 2, 1), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 2)