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

Question

我有以下问题可归纳如下：

想象一下，你有两个大于0的整数，N（定义数组n=np.array(range(N)）和M.我们想要生成长度为M的n元素的所有可能组合，条件是没有相等的元素是连续的。

例如，对于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)

Answer 2

您所描述的是通过使用Python（功能强大的）itertools库然后根据您的条件过滤掉来实现的。但你想要的只是产品而不是阵列的组合。

这是一种方法，假设参数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]]。现在，您可以按照所需的标准过滤这些内容。

在您的情况下，“没有重复元素连续”等于检查两个连续元素之间的差异是否永远不为零。所以我们得到了差异：

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 yiels：

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]])