来自 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 为底数的数字，但在玩了一段时间后我没有找到任何有用的东西。

如有任何帮助，我将不胜感激，在此先致谢（很抱歉 post）！

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)

Answer 2

您所描述的可以通过使用 Python 的（强大的）itertools 库然后根据您的条件过滤掉来实现。但是你想要的是 product 而不是数组的 combination.

这是一种方法，假设参数 N 和 M。

import numpy as np
import itertools

p = np.arange(N)

获取长度为3的乘积：

product_iterator = itertools.product(p, repeat=M)

这为您提供了一个迭代器对象。你可以从中得到一个具体的列表（并立即把它变成一个数组，在这个例子中，虽然我称之为列表）：

product_list = np.array(list(product_iterator))

此时你得到了所有 27 种组合的数组：[ [0 0 0], [0 0 1], [0 0 2], ..., [2 2 1], [2 2 2 ] ].现在您可以按所需的标准过滤这些。

在您的情况下，'no repeated elements consecutive' 相当于检查两个连续元素之间的差异是否永远不为零。所以我们得到了差异：

diffs = np.diff(product_list,axis=1)

这产生：

[[ 0  0]
 [ 0  1]
 [ 0  2]
 [ 1 -1]
 [ 1  0]
 [ 1  1]
 [ 2 -2]
 [ 2 -1]
 [ 2  0]
 [-1  0]
 [-1  1]
 [-1  2]
 [ 0 -1]
 [ 0  0]
 [ 0  1]
 [ 1 -2]
 [ 1 -1]
 [ 1  0]
 [-2  0]
 [-2  1]
 [-2  2]
 [-1 -1]
 [-1  0]
 [-1  1]
 [ 0 -2]
 [ 0 -1]
 [ 0  0]]

现在我们逐行检查是否有零：

no_consec_indexes = np.apply_along_axis(lambda x: np.all(x), 1, diffs)

这会产生一个布尔值数组 no_consec_indexes：

array([False, False, False,  True, False,  True,  True,  True, False,
       False,  True,  True, False, False, False,  True,  True, False,
       False,  True,  True,  True, False,  True, False, False, False])

你可以用它来过滤掉原来的产品数组：

product_list[no_consec_indexes]

这会产生您想要的答案：

 array([[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]])

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

Combinations of M elements from N with non consecutive repetitions

python

recursion

for-loop

numpy

combinatorics