N个嵌套的for循环

Question

我需要创建N个嵌套循环来打印长度为N的二进制序列的所有组合。我不确定如何做到这一点。

任何帮助将不胜感激。谢谢。

- BluffTrout

---

很可能是Java。我只需要想出伪代码，一旦有了解决方案，我就可以将其粘贴到任何语言中。 - BluffTrout

像这样吗？https://dev59.com/TW445IYBdhLWcg3wTInm#4928350 - Josh Bleecher Snyder

我对Python不是很熟悉。我不确定你对那个问题的回答是在做什么。你是在硬编码所有可能性吗？ - BluffTrout

Answer 1

使用递归。例如，在Java中：

public class Foo {

   public static void main(String[] args) {
      new Foo().printCombo("", 5);
   }

   void printCombo(String soFar, int len) {
      if (len == 1) {
         System.out.println(soFar+"0");
         System.out.println(soFar+"1");
      }
      else {
         printCombo(soFar+"0", len-1);
         printCombo(soFar+"1", len-1);
      }         
   }
}

将会打印出以下内容： 00000 00001 00010 ... 11101 11110 11111

- user949300

---

这个可能行。我会尝试将其实现到我的算法中，并回复你。 - BluffTrout

@BluffTrout：这会起作用，因为递归是解决这个问题的方法。 - Ed S.

@BluffTrout 根据您用于确定是否为可行解的标准，您可以在printCombo()的开头添加一个检查，例如：if (notFeasable(soFar)) return; - user949300

这个非常好用。我已经成功修改它以符合我所需要的内容。感谢大家的帮助 :) - BluffTrout

Answer 2

你有两个选择：

1. 改用回溯法。
2. 编写一个生成具有N个循环的动态程序并执行它的程序。

- Tudor

---

我认为回溯法不正确，因为只有在某些解决方案不可能时才适用。我认为你所指的应该是递归。 - user949300

是的，实际上我指的是递归回溯。此外，您可以使用带有空验证函数的回溯，即接受任何生成的解决方案。 - Tudor

Answer 3

你不需要嵌套循环来实现这个。你只需要一个递归函数来打印长度为N的二进制值，再用一个for循环遍历所有数字[0 .. (2^N)-1]。

user949300的解决方案也很好，但可能在某些语言中无法正常工作。

这是我的解决方案，递归方法大约比迭代方法慢两倍：

#include <stdio.h>

#ifdef RECURSIVE
void print_bin(int num, int len)
{
   if(len == 0)
   {
      printf("\n");
      return;
   }

   print_bin(num >> 1, len -1);
   putchar((num & 1) + '0');
}
#else
void print_bin(int num, int len)
{
    char str[len+1];
    int i;

    str[len] = '\0';

    for (i = 0; i < len; i++)
    {
       str[len-1-i] = !!(num & (1 << i)) + '0';
    }

    printf("%s\n", str);
}
#endif

int main()
{
   int len = 24;
   int i;
   int end = 1 << len;

   for (i = 0; i < end ; i++)
   {
      print_bin(i, len);
   }

   return 0;
}

我在 Mac 上尝试打印长度为 24 的所有二进制数字，结果终端程序挂了。但这可能是终端实现较差的缘故。 :-)

$ gcc -O3 binary.c ; time ./a.out > /dev/null ; gcc -O3 -DRECURSIVE binary.c ; time ./a.out > /dev/null 

real        0m1.875s
user        0m1.859s
sys         0m0.008s

real        0m3.327s
user        0m3.310s
sys         0m0.010s

- onemasse

---

哎呀，那可能行不通。就我正在创建的程序而言，我需要逐个遍历每个组合，并查看它是否是另一个问题的可行解决方案。它不一定需要一次性计算所有组合。 - BluffTrout

我认为算法本身没有任何问题，但是Terminal.app处理历史记录的能力可能存在问题。 - onemasse

对于很大的N，我的算法可能会耗尽内存。 - user949300

因此，对于较大的N，请通过单个for-next循环更明确地执行，并在Java中使用Integer.toString（theValue，2）;与此处提出的相同思路（https://dev59.com/TW445IYBdhLWcg3wTInm#4928336）。 - user949300

Answer 4

我认为我们不需要使用递归或n个嵌套的for循环来解决这个问题。使用位运算处理这个问题将会更容易。

以C++为例：

for(int i=0;i<(1<<n);i++)
{
  for(int j=0;j<n;j++)
    if(i&(1<<j))
      printf("1");
    else
      printf("0");
  printf("\n");
}

- derekhh