所有可能的 N 选择 K 没有递归

Question

我正在尝试创建一个函数，该函数能够遍历行向量并输出 n choose k 的可能组合而无需递归 。

例如：3在[a,b,c]上选择2输出[a,b;一、三； b,c]

我发现了这个：How to loop through all the combinations of e.g. 48 choose 5 which shows how to do it for a fixed n choose k and this: https://codereview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array 它展示了如何获得所有可能的组合。使用后面的代码，我设法在 matlab 中创建了一个非常简单且效率低下的函数，该函数返回了结果：

function [ combi ] = NCK(x,k)
%x - row vector of inputs
%k - number of elements in the combinations

combi = [];
letLen = 2^length(x);

for i = 0:letLen-1

    temp=[0];
    a=1;

    for j=0:length(x)-1

        if (bitand(i,2^j))
            temp(k) = x(j+1);
            a=a+1;
        end
    end

    if (nnz(temp) == k)
        combi=[combi; derp];
    end
end
combi = sortrows(combi);
end

这适用于非常小的向量，但我需要它能够处理长度至少为 50 的向量。我发现了很多关于如何递归执行此操作的示例，但是是否有一种有效的方法可以在不递归的情况下执行此操作并且仍然能够执行可变大小的向量和 ks？

Answer 1

这是一个简单的函数，它将采用 k 个和 n-k 个零以及 return nchoosek 的下一个组合的排列。它完全独立于 n 和 k 的值，直接从输入数组中获取值。

function [nextc] = nextComb(oldc)
   nextc = [];
   o = find(oldc, 1);                 %// find the first one
   z = find(~oldc(o+1:end), 1) + o;   %// find the first zero *after* the first one
   if length(z) > 0
      nextc = oldc;
      nextc(1:z-1) = 0;
      nextc(z) = 1;                   %// make the first zero a one
      nextc(1:nnz(oldc(1:z-2))) = 1;  %// move previous ones to the beginning
   else
      nextc = zeros(size(oldc));
      nextc(1:nnz(oldc)) = 1;         %// start over
   end
end

（请注意，仅当您希望组合从最后一个组合到第一个组合时才需要 else 子句。）

如果您调用此函数，例如：

A = [1 1 1 1 1 0 1 0 0 1 1]
nextCombination = nextComb(A)

输出将是：

A =

   1   1   1   1   1   0   1   0   0   1   1

nextCombination =

   1   1   1   1   0   1   1   0   0   1   1

然后您可以将其用作字母表（或您想要组合的任何元素）的掩码。

C = ['a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 'j' 'k']
C(find(nextCombination))

ans = abcdegjk

此顺序中的第一个组合是

1   1   1   1   1   1   1   1   0   0   0

最后一个是

0   0   0   1   1   1   1   1   1   1   1

要以编程方式生成第一个组合，

n = 11; k = 8;
nextCombination = zeros(1,n);
nextCombination(1:k) = 1;

现在您可以遍历组合（或者您愿意等待的组合）：

for c = 2:nchoosek(n,k)   %// start from 2; we already have 1
   nextCombination = nextComb(A);
   %// do something with the combination...
end

对于上面的示例：

nextCombination = [1 1 0];
C(find(nextCombination))
for c = 2:nchoosek(3,2)
   nextCombination = nextComb(nextCombination);
   C(find(nextCombination))
end

ans = ab
ans = ac
ans = bc

注意：我已经更新了代码；我忘记包含将交换数字之前出现的所有 1 移动到数组开头的行。当前代码（除了上面已更正的代码）在 ideone here 上。 4 choose 2 的输出是：

所有可能的 N 选择 K 没有递归

All possible N choose K WITHOUT recusion

algorithm

matlab

combinations