所有可能ñ选择Kb无recusion [英] All possible N choose K WITHOUT recusion

问题描述

我试图创建一个函数，能够通过一个行向量和输出的可能组合ñ选择k 不递归。

I'm trying to create a function that is able to go through a row vector and output the possible combinations of an n choose k without recursion.

例如：3选2的[A，B，C]输出[A，B; A，C; B，C]

For example: 3 choose 2 on [a,b,c] outputs [a,b; a,c; b,c]

我发现这一点：<一href="http://stackoverflow.com/questions/8375452/how-to-loop-through-all-the-combinations-of-e-g-48-choose-5">How通过对例如所有组合循环48选5 它展示了如何做到这一点的定氮条件选择k和这样的：<一href="http://$c$creview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array">http://$c$creview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array这说明如何获得所有可能的组合。使用后者code，我设法在MATLAB一个非常简单的和低效的功能，返回的结果：

I found this: 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: http://codereview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array which shows how to get all possible combinations. Using the latter code, I managed to make a very simple and inefficient function in matlab which returned the result:

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？

This works well for very small vectors, but I need this to be able to work with vectors of at least 50 in length. I've found many examples of how to do this recursively, but is there an efficient way to do this without recursion and still be able to do variable sized vectors and ks?

推荐答案

下面是一个简单的函数，将采取 K 1和 NK的置换零和返回 nchoosek 的下一个组合。它是完全独立的价值观 N 和 K ，直接从输入数组取值。

Here's a simple function that will take a permutation of k ones and n-k zeros and return the next combination of nchoosek. It's completely independent of the values of n and k, taking the values directly from the input array.

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

（请注意，如果你想组合从最后结合到第一个环绕其他子句才是必需的。）

(Note that the else clause is only necessary if you want the combinations to wrap around from the last combination to the first.)

如果你调用该函数，例如：

If you call this function with, for example:

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

（你想要的组合或其他元素）然后，您可以使用它作为一个面具到您的字母表。

You can then use this as a mask into your alphabet (or whatever elements you want combinations of).

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

ans = abcdegjk

在此排序的第一个组合是

The first combination in this ordering is

1   1   1   1   1   1   1   1   0   0   0

和最后才是

0   0   0   1   1   1   1   1   1   1   1

要编程生成的第一组合，

To generate the first combination programatically,

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

现在，你可以通过组合迭代（或包含很多你愿意等待）：

Now you can iterate through the combinations (or however many you're willing to wait for):

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

---

注意：我已经更新了code;我忘了包括线路将所有之前交换数字到数组的开头出现1的的。目前的code（除上述被纠正）是ideone 这里。输出 4选2 是：

---

Note: I've updated the code; I had forgotten to include the line to move all of the 1's that occur prior to the swapped digits to the beginning of the array. The current code (in addition to being corrected above) is on ideone here. Output for 4 choose 2 is:

allCombs =

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

这篇关于所有可能ñ选择Kb无recusion的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！