用于生成任意位数0和1的所有可能组合的算法

Question

我想知道如何打印n个由1和0组成的组合。组合数n由用户定义。预期输出为:

n=1;

0,1

n=2;

00,01,10,11

n=3;

000,001,010,011,100,101,110,111

输出结果将有2^n个组合（其中n是单个组合中预期数字的数量）。

如何在不使用任何内置函数的情况下实现此操作？该问题与语言无关且涉及算法。

- Alfred

---

为什么是-1？这个问题是真实的并且是“在”主题上的。 - Alfred

重要提示：您实际上正在讨论排列而不是组合！ - Pinna_be

Answer 1

您可以直接枚举从0到2的n次方减1的所有数字的二进制表示，这将得到相同的组合。

例如当n等于2时，枚举从0到2的3次方减1的数字，即0, 1, 2, 3, 4, 5, 6, 7，然后转换成二进制即可。

000 --> 0
001 --> 1
010 --> 2
011 --> 3
100 --> 4
101 --> 5
110 --> 6
111 --> 7

编辑：已修正数字的位数。这个方法有效。

#include <stdio.h>
#define LENGTH 3
void print_binary(int n)
{
        int bit = 1<<LENGTH - 1;
        while ( bit ) {
        printf("%d", n & bit ? 1 : 0);
        bit >>= 1;
        }
        printf("\n");
}
int main(){
    int n = 1<<LENGTH, i; 
    for(i=0;i<n;i++)
        print_binary(i);
}

- Anirudh Ramanathan

---

请问您能否提供一个在C语言中工作的示例，而不使用任何特殊的内置函数？ - Alfred

如果是这样的话，我认为会打印出0、1、10和11，而不是000、001、010和011。 - Alfred

不，不是这样。您可以根据需要在前面添加0以获得正确的长度。您要求一个算法，他给了您一个算法。那您为什么不自己实现呢？！ - thang

用“n=(1<<LENGTH)”替换第一个for循环。 - thang

@thang 很好 :) 谢谢。 - Anirudh Ramanathan

Answer 2

如果您不关心速度和内存，您可以使用递归来实现一个简短的解决方案：

public static void print01PermutationsUpToLength(final String currentString, final int upTo) {
    if (upTo == 0) {
        System.out.println(currentString);
        return;
    }
    print01PermutationsUpToLength(currentString + "0", upTo - 1);
    print01PermutationsUpToLength(currentString + "1", upTo - 1);
}

（Java。显然，这可以在允许递归和按值调用或复制字符串的每种语言中完成）

如果您不喜欢String参数，可以添加一个开始函数：

public static void print01PermutationsUpToLength(final int upTo) {
    print01PermutationsUpToLength("", upTo);
}

成果:

final int upToLength = 3;
print01PermutationsUpToLength(upToLength);
000
001
010
011
100
101
110
111

格式可以按照您的喜好进行更改，这只是为了更好地查看结果。
如果您交换字符串构造部分（currentString + "0"），则可以更改排序。

- tb-

Answer 3

void print_digit(int n,int digits)
{
   int i;
   for(i=0;i<digits;i++)
   { 
       if(n&(1<<(digits-i-1)))
       {
           putchar('1');
       }
       else
       {
           putchar('0');
       }
   }
}

print all_digits(int e)
{
   for(i=0;i<(1<<e);i++)
   {
        print_digit(i,e);
        putchar('\n');
   }
   fflush(stdout);
}

- Luka Rahne

---

我认为你不需要（e+1）。只有n就可以了。 - thang

e就像指数。输入值是幂，比如3或4。 - Luka Rahne

是的，但如果调用all_digits(1)，你会输出两倍于所需的字符串。我想这没关系，只是不符合要求。 - thang

Answer 4

这是我对这个问题的看法。给定一个字符数组，您想使用整个数组找到k个组合。

为了解决这个问题，我们的数组包含：['0'，'1']。

假设我们有一个char set [] = new {'0'，'1'};

下面的方法将为您提供任意数量的零和一的组合。我已经使用50个字符的数据集测试了它与0和1的组合。

public  void printLengthRec(char[] inputSet, String prefix, int k) {
    int sizeOfInputArray=inputSet.length;
    //TerminationCase: k is 0, print prefix
    if (k == 0) {
        System.out.println(prefix);
        return;
    }    
    // One by one add all characters from set and recursively 
    // call for k equals to k-1
    for (int i = 0; i < 2; ++i) {
        // Next character of input added
        String newPrefix = prefix + set[i]; 
        printLengthRec(inputSet, newPrefix, k - 1); 
    }
} 

- Andy