如何计算满足给定条件的向量的所有置换

Question

我想一次计算向量N的所有置换k。我还想允许N的任何元素与其自身而不仅仅与其他元素交换。我只想得到求和到给定数n的排列。你知道吗

以下是MATLAB中的一个示例：

N = [1 2 3 4];
k = 2;
n = 6;

对于以上数字，我可以通过以下方式达到目标：

Perm = combvec(N, N)';
Perm = Perm(sum(Perm,2)==n,:);
Perm =

     4     2
     3     3
     2     4

但是，N的长度预计可达90个元素，k的值预计可达10。这使得上述方法不可行，因为它涉及许多不需要的排列的计算。你知道吗

有没有任何方法可以有效地做到这一点，因为预期的N向量长度和k？我很乐意考虑使用MATLAB、R或python的解决方案。你知道吗

Answer 1

这是一个基于生成器的尝试，它只是一次生成一个置换，而不是将它们全部存储在内存中。我使用了生成器方法，因为我认为任何其他方法都会耗尽内存，只要k大于5，排列的数量就会很大：

def find_perm(k, n, N=None):
    # Initialize N
    if N is None:
        N = list(range(1, n - k + 1))

    if k == 0:
        return []

    # Only search up to n (the current target)
    for i in N[:(n + 1)]:
        if i > n:
            continue
        if i == n:
            yield [i]
            continue
        # Recurse
        sub_perms = find_perm(k - 1, n - i, N[:(n + 1)])

        for sub_perm in sub_perms:
            perm = [i] + sub_perm
            if sum(perm) == n:
                yield perm

输出示例：

list(find_perm(2, 6))
# [[2, 4], [3, 3], [4, 2]]

# Too many to store, just printing a few
big_perms = find_perm(10, 100)
for i in range(5):
    print(next(big_perms))
# [1, 1, 1, 1, 1, 1, 1, 1, 2, 90]
# [1, 1, 1, 1, 1, 1, 1, 1, 3, 89]
# [1, 1, 1, 1, 1, 1, 1, 1, 4, 88]
# [1, 1, 1, 1, 1, 1, 1, 1, 5, 87]
# [1, 1, 1, 1, 1, 1, 1, 1, 6, 86]

Answer 2

似乎你的问题是，是否有一种有效的方法来找到{1，2，…，90}的所有10个元素子集，允许重复，求和为100。你知道吗

很容易计算出存在多少这样的子集：

N <- 1:90  # values we can select
k <- 10  # num to select (repeats allowed)
n <- 100  # target
num <- matrix(NA, n, k) # (i,j) is number of subsets of size j summing to i
num[,1] <- as.numeric(1:n %in% N)  # base case
for (kval in 2:k) {
  num[,kval] <- sapply(1:n, function(jval) {
    sum(num[intersect(1:n, jval-N),kval-1])
  })
}
num[n,k]  # Number of combinations
# [1] 1.731031e+12

所以你在问，是否有一种有效的方法来计算和输出一组1.73万亿长度的向量。我认为答案是否定的，这是一个天文数字的向量输出，存储或操纵。你知道吗