algorithm - 所有可能的 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它显示了如何为固定的 n 选择 k 和这个: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 个零进行排列，并返回 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 的输出是:

allCombs =

   1   2
   1   3
   2   3
   1   4
   2   4
   3   4