所有可能的N选择K，无回音

小编典典

所有可能的N选择K，无回音

algorithm

我正在尝试创建一个能够通过行向量并输出n选择k的可能组合 而无需递归 的函数。

例如：3在[a，b，c]输出[a，b]上选择2；a，c; 公元前]

我发现了这一点：如何遍历例如48选择5的所有组合，
这显示了如何针对固定n选择k，显示如何获取所有可能的组合。使用后面的代码，我设法在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？

阅读 296

2020-07-28

共1个答案

小编典典

这是一个简单的函数，它将对k1和n-k0 进行排列并返回的下一个组合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
。输出为4 choose 2：

2020-07-28