algorithm - 递归生成所有长度为 n 的二进制字符串的最佳方法是什么？

Question

我正在寻找一种好的（易于实现、直观等）递归方法来生成所有长度为 的二进制字符串n，其中1 <= n <= 35.

我会很感激关于伪代码算法的想法（没有特定于语言的技巧）。

LE: 好吧，我确实超出了上限。我的意图是避免使用从1to计数器的二进制表示的解决方案1 << n。

Answer 1

这是 C++ 中的递归示例。

vector<string> answer;

void getStrings( string s, int digitsLeft )
{
   if( digitsLeft == 0 ) // the length of string is n
      answer.push_back( s );
   else
   {
      getStrings( s + "0", digitsLeft - 1 );
      getStrings( s + "1", digitsLeft - 1 );
   }
}

getStrings( "", n ); // initial call

Answer 2

根据 Divide et Impera 范式，生成所有长度为 n 的二进制字符串的问题可以分为两个子问题：打印所有长度为 n-1 且前面有 0 的二进制字符串的问题和打印所有长度为 n-1 的二进制字符串的问题。长度 n-1 前面是 1。所以下面的伪代码解决了这个问题：

generateBinary(length, string)

if(length > 0)
    generateBinary(length-1, string + "0")
    generateBinary(length-1, string + "1")
else
    print(string)

Answer 3

def genBins(n):
    """
       generate all the binary strings with n-length
    """
    max_int = '0b' + '1' * n
    for i in range(0, int(max_int, 2)+1, 1):
        yield str(format(i, 'b').zfill(n))

if __name__ == '__main__':

    print(list(genBins(5)))

Answer 4

您遇到的问题可以通过回溯算法来解决。

这种算法的伪代码是：

fun(input, n) 
    if( base_case(input, n) ) 
        //print result
    else
        //choose from pool of choices
        //explorer the rest of choices from what's left
        //unchoose

执行：

• 基本情况：我们希望在其大小等于n时打印我们的结果字符串
• 递归案例：
  • 我们的选择池由0和1组成
  • 在这种情况下选择意味着取 0 或 1 并将其作为最后一个字符添加到输入中
  • 通过递归探索，我们从选择步骤传递新的输入值，直到达到基本情况
  • 在这种情况下取​​消选择意味着删除最后一个字符

function binary(n) {
  binaryHelper('', n);
}

function binaryHelper(str, n) {
  if (str.length === n) {
    //base case
    console.log(str); //print string
  } else {
    for (let bit = 0; bit < 2; bit++) {
      str = str + bit; // choose
      binaryHelper(str, n); // explore
      str = str.slice(0, -1); // un-choose
    }
  }
}

console.log('Size 2 binary strings:');
binary(2);
console.log('Size 3 binary strings:');
binary(3);

您可以像这样重写上面的代码，通过从一个循环迭代到另一个循环迭代的无状态转换来选择和取消选择。不过，这不太直观。

function binary(n) {
  binaryHelper('', n);
}

function binaryHelper(str, n) {
  if(str.length === n) {
    console.log(str);
  } else {
    for(let bit = 0; bit < 2; bit++) {
      binaryHelper(str+bit, n);
    }
  }
}

console.log('Size 2 binary strings:');
binary(2);
console.log('Size 3 binary strings:');
binary(3);