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

Question

我正在寻找一个很好(易于实现、直观等)的递归方法，用于生成长度为n的所有二进制字符串，其中1 <= n <= 35。

我希望有一个伪代码算法的想法(没有特定于语言的技巧)。

莱:好吧，我的确是在上限问题上做得太过分了。我的目的是避免使用从1到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范式，所有长度为n的二进制字符串的生成问题可分为两个子问题:打印n-1长度为0的所有二进制字符串的问题和打印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)))