7

5 つの 0 の文字列の順列に続いて 4 つの 0 と 1 つの 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

1 つのアプローチは次のとおりです。このソリューションには 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 に答える