7

我想生成 5 个 0 的字符串的排列，然后是 4 个 0 和一个 1 的排列，然后是 3 个 0 和 2 个 1 的排列，等等？我的代码如下：

#include<stdio.h>
int main(){

int i,j,k,l,s[5];
for(i=0;i<5;i++)
  s[i]=0;
for(k=0;k<5;k++)
       printf("%d  ",s[k]);
   printf("\n");
printf("---------------------------------------------\n");

for(i=0;i<5;i++){
  for(j=0;j<5;j++)
    if(i==j)
      s[j]=1;

    else
      s[j]=0;
    for(k=0;k<5;k++)
       printf("%d  ",s[k]);
   printf("\n");
                 }
printf("---------------------------------------------\n");

for(i=0;i<5;i++){
  for(k=0;k<5;k++)
    s[k]=0;
  s[i]=1;
  for(j=i+1;j<5;j++){
    s[j]=1;
    for(k=0;k<5;k++)
       printf("%d  ",s[k]);
    printf("\n");
    for(k=j;k<5;k++)
       s[k]=0;
                    }

                 }

printf("---------------------------------------------\n");
for(i=0;i<5;i++){

  for(j=i+1;j<5;j++){
    for(k=0;k<5;k++)
       s[k]=0;
    s[i]=1;
    s[j]=1;
    for(l=j+1;l<5;l++){
        s[l]=1;
    for(k=0;k<5;k++)
       printf("%d  ",s[k]);
    printf("\n");
    for(k=l;k<5;k++)
       s[k]=0;
                      }
                    }

                 }


}

所以输出是 

0  0  0  0  0  
---------------------------------------------
1  0  0  0  0  
0  1  0  0  0  
0  0  1  0  0  
0  0  0  1  0  
0  0  0  0  1  
---------------------------------------------
1  1  0  0  0  
1  0  1  0  0  
1  0  0  1  0  
1  0  0  0  1  
0  1  1  0  0  
0  1  0  1  0  
0  1  0  0  1  
0  0  1  1  0  
0  0  1  0  1  
0  0  0  1  1  
---------------------------------------------
1  1  1  0  0  
1  1  0  1  0  
1  1  0  0  1  
1  0  1  1  0  
1  0  1  0  1  
1  0  0  1  1  
0  1  1  1  0  
0  1  1  0  1  
0  1  0  1  1  
0  0  1  1  1

输出没问题。但是在我的代码中，我对不同的情况使用不同的 for 循环。是否可以使用更好的方法来减少代码的长度？

4

2 回答 2

6

一种方法如下。该解决方案需要 O(n) 空间，每个输出字符串需要 O(n) 时间。

#include <stdio.h>
#include <stdlib.h>

char *buf;

// Print combinations of m 1's in a field of n 0/1's starting at s.
void print_combinations(char *s, int n, int m)
{
  // If there is nothing left to append, we are done.  Print the buffer.
  if (m == 0 && n == 0) {
    *s = '\0';
    printf("%s\n", buf);
    return;
  }
  // Cut if there are more 1's than positions left or negative numbers.
  if (m > n || m < 0 || n < 0) return;
  // Append a 0 and recur to print the rest.
  *s = '0';
  print_combinations(s + 1, n - 1, m);
  // Now do the same with 1.
  *s = '1';
  print_combinations(s + 1, n - 1, m - 1);
}

int main(void)
{  
  int n = 5;
  buf = malloc(n + 1);
  for (int m = 0; m <= n; m++) {
    print_combinations(buf, n, m);
    printf("-----\n");
  }
  return 0;
}
于 2013-05-29T00:56:39.067 回答
2

您可以使用这样的递归函数 - 您不必在完成后打印结果，您可以将其添加到列表等。

该函数以空字符串开头。在每一步中，您都添加了一个字符 - 在这种情况下，您添加了 a0或 a 1。

如果添加了 a ，我们会通过在下一次调用该函数时1递减值来解决此问题。ones（在更一般的情况下，您可以传递要排列的所有元素的列表 - 然后该过程将从该列表中选择，将其添加到您的排列中并将其从列表中删除。您重复此操作直到列表为空并且您已经排列了列表中的所有元素。）

当字符串达到所需的长度时，我们已经完成，所以我们返回。

#include <stdio.h>

void recurse(char *str, int length, int maxLength, int ones)
{
    if (length == maxLength)
    {
        // we are finished
        printf("%s\n", str);
        return;
    }

    if (ones > 0)
    {
        // put a 1 into the new string
        str[length] = '1';
        recurse(str, length + 1, maxLength, ones - 1);
    }

    if (ones < maxLength - length)
    {
        // there are still spaces for 0s
        // put a 0 into the string
        str[length] = '0';
        recurse(str, length + 1, maxLength, ones);
    }
}

int main()
{
    const int maxLength = 5;
    char buffer[maxLength + 1];
    buffer[maxLength] = 0;

    int ones;
    for (ones = 0; ones <= maxLength; ones++)
    {
        printf("Ones: %i\n", ones);
        recurse(buffer, 0, maxLength, ones);
        printf("\n");
    }

    return 0;
}

输出如下所示：

Ones: 0
00000

Ones: 1
10000
01000
00100
00010
00001

Ones: 2
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

Ones: 3
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111

Ones: 4
11110
11101
11011
10111
01111

Ones: 5
11111

最后，除非您真的想/需要学习/使用 C，否则我建议您使用 C++，因为您可以获得非常好的功能，例如std::vector等等std::set，这将使您的生活变得更加轻松。我会用 C++ 完全不同地写这个。

于 2013-05-29T00:45:40.180 回答