生成所有具有重复数字的组合

Question

我已经阅读这个网站足够长的时间了，知道不要隐瞒这是一项家庭作业。但我正在尝试编写一个代码，可以生成仅由 0 和 1 组成的字符串的所有可能组合。如果字符串的长度是n^2，那么就会有n个1，其余的都是0。长度始终是完全平方数。我正在用 C 进行编码，我一直在尝试在嵌套循环中完成它，但似乎可以通过递归方式更轻松地完成它，我只是不确定如何进行设置。任何提示或建议将不胜感激。

Answer 1

伪代码：

myfun(pos,length, ones)
  if (length==0)
     pos='\0'
     #print, collect, whatever...
     return
  if (length>ones)
    pos='0'
    myfun(pos+1,length-1, ones)
  pos='1'
  myfun(pos+1, length-1, ones-1)

task(n)
  #allocate n^2 buffer
  myfun(buffer, n*n, n)

Answer 2

我不确定这个问题是否适合递归。在 C（和大多数语言）中，每次调用函数时，都会创建一个堆栈帧并使用几个处理器周期和一块堆栈内存。此问题的任何递归解决方案都会创建 n^2 堆栈帧，即使递归本身仅添加一位信息。

下面概述了一个非常糟糕的解决方案。它不做什么：

• 利用 n 始终是完全平方这一事实。
• 以非常智能的方式使用内存
• 释放它使用的任何内存
• 甚至可能不起作用。 ;)

...但它可能会让您了解基本模式。

void foo(int zeros_left, int length_left, char *s)
{
    if (length_left == 0)
        printf("%s\n", s);
    else
    {
        if (zeros_left > 0)
        {
            char *next = malloc(strlen(s) + 2);
            strcpy(next, s);
            strcat(next, "0");
            foo(zeros_left - 1, length_left - 1, next);
        }

        if (zeros_left != length_left)
        {
            char *next = malloc(strlen(s) + 2);
            strcpy(next, s);
            strcat(next, "1");
            foo(zeros_left, length_left - 1, next);
        }
    }
}

Answer 3

对问题进行递归建模的关键是将问题的较大版本分解为与同一问题的较小版本相结合的简单计算，以及终止递归的简单情况。

在这种情况下，问题是：

• 对于非负的M和N，输出所有长度为M且恰好包含N个1的字符串。

您可以将其分解为：

• 如果M = 0，则输出一个空字符串；否则
• 输出长度为 M-1 且恰好包含 N 1 的所有字符串，每个字符串都以 0 为前缀；如果
• N > 0，然后输出长度为 M-1 且正好包含 N-1 1 的字符串，每个字符串都以 1 为前缀。

这里，M = 0 是终止递归的简单情况。将以上内容转化为代码相当简单。