按位移位以在C中生成所有可能的排列

Question

可能重复:
创建具有特定位数的多个数字

我正在尝试编写一些代码,通过将位移位来将每个可能的数字组合放在一个数组中.

例如,我想找到数组应该包含的3位(最大数字可以是6)的所有可能组合:

000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011

等等...

根据我的解释,当最后一个位置为1时,我们将数字移1(x >> 1)并在开始时加1.但是,我不确定如何编写其余的代码.我用C来写这个.

另外 - 据我所知,这是一个colex序列,但是,如果有另一个序列可以给我相同的最终结果(具有约束为N的k位的所有可能组合的数组),我都是耳朵. .

Answer 1

您可以通过递归生成序列来解决此问题.

让我们定义一个递归函数f(int index, int bits, int number),它将获取位的当前index位置和bits左边的位数,以及number到目前为止生成的.然后,您可以选择将当前位设置为1或0,并从那里进行递归.

总的来说,时间复杂度应为O(序列数)或O(N选择B),其中N是数字位数,B是设置为1的位数.

功能如下:

void f(int index, int bits, int number) {
    if (index == 0) {
        if (bits == 0) {   // all required bits have been used
            emit_answer(number); // chuck number into an array, print it, whatever.
        }   
        return;
    }   

    if (index-1 >= bits) {  // If we can afford to put a 0 here
        f(index-1, bits, number);
    }   

    if (bits > 0) {  // If we have any 1s left to place
        f(index-1, bits-1, number | (1 << (index-1)));
    }   
}

// to call:
f(6, 3, 0); 

对于N,B = 6,3输出匹配你的,是按排序顺序.链接到工作示例:http://codepad.org/qgd689ZM