I'm trying to build a program to enumerate all the possible strings on a given alphabet. I plan to use distributed and parallel techniques on the algorithm afterwards so recursion is not an option. So far what I tried is something like that:

const char alph[] = "01";

char **
generate(int size)
{
    int i, j, k;
    char str[10];

    memset(str, alph[0], size);
    str[size] = '\0';

    for (i = size-2; i >= -1; --i) {
        for (j = size-1; j > i; --j) {
            for (k = 0; k < strlen(alph); k  ) {                
                str[j] = alph[k];
                printf("%s\n", str);
            }
        }
    }
}

So generate(2) should result on {00, 01, 10, 11}. But on current implementation I get {00, 01, 00, 01, 01, 11}. I suppose that's a problem with the indexes but I can't find which one.

CodePudding user response：

Simple solution for size 2

Here is a simple solution but it only works for size 2:

#include <stdio.h>
#include <string.h>

const char alph[] = "01";

// Note: This only works for size 2
void generate(int size) {
  char str[10];
  str[size] = 0;
  for (int i = 0; i < strlen(alph); i  ) {
    str[0] = alph[i];
    for (int j = 0; j < strlen(alph); j  ) {
      str[1] = alph[j];
      printf("%s\n", str);
    }
  }
}

int main() {
  generate(2);
}

There are two nested loops and each loop corresponds to one of the positions in the output string. If you wanted to increase the length of the output string, the general idea is to add more loops. Usually, recursion is used to do that, but you prohibited recursion in your question.

More general solution

Here is a more general solution which does a lot more work, but is easier to parallelize. It calculates the number of lines in the output first, and then calls print_line to print each line. The calls to print_line could all be running in parallel, I suppose, as long as you do something to make sure output is printed in the desired order.

#include <stdio.h>
#include <string.h>
#include <stdint.h>

const char alph[] = "01";

void print_line(uint64_t v, int size)
{
  char str[size   1];
  str[size] = 0;
  for (int i = size - 1; i >= 0; i--)
  {
    str[i] = alph[v % strlen(alph)];
    v /= strlen(alph);
  }
  printf("%s\n", str);
}

void generate(int size) {
  uint64_t output_line_count = 1;
  for (int i = 0; i < size; i  ) { output_line_count *= strlen(alph); }

  for (uint64_t v = 0; v < output_line_count; v  )
  {
    print_line(v, size);
  }
}

int main() {
  generate(3);
}