生成给定长度的1和0的所有可能数组的算法

Question

如何在长度为n的位数组中生成所有可能的位组合.如果我从我的数组中的所有零开始,则有n种可能性放置第一位,并且对于这n种可能性,存在n-1种可能性来放置第二位.单位所有n位被设置为1.但到目前为止,我没有设法编程.

还有很多人指出我可以通过从0到(2 ^ n)-1计数并以二进制打印数字来做到这一点.这将是一种解决问题的简单方法,但是在这种情况下,我只是让机器计数而不是告诉它放置在哪里.我这样做是为了学习,所以我想知道如何编制一个放置方法.

Answer 1

你会如何在纸上手动计算？你会检查最后一位数.如果为0,则将其设置为1.如果已经为1,则将其设置为0并继续下一个数字.所以这是一个递归过程.

以下程序通过改变序列来生成所有可能的组合:

#include <iostream>

template <typename Iter>
bool next(Iter begin, Iter end)
{
    if (begin == end)      // changed all digits
    {                      // so we are back to zero
        return false;      // that was the last number
    }
    --end;
    if ((*end & 1) == 0)   // even number is treated as zero
    {
        ++*end;            // increase to one
        return true;       // still more numbers to come
    }
    else                   // odd number is treated as one
    {
        --*end;            // decrease to zero
        return next(begin, end);   // RECURSE!
    }
}

int main()
{
    char test[] = "0000";
    do
    {
        std::cout << test << std::endl;
    } while (next(test + 0, test + 4));
}

该程序适用于任何类型的任何序列.如果您需要同时进行所有可能的组合,只需将它们放入集合中而不是将它们打印出来.当然,您需要一个不同的元素类型,因为您不能将C数组放入向量中.让我们使用字符串向量:

#include <string>
#include <vector>

int main()
{
    std::vector<std::string> combinations;
    std::string test = "0000";
    do
    {
        combinations.push_back(test);
    } while (next(test.begin(), test.end()));
    // now the vector contains all pssible combinations
}

如果你不喜欢递归,这里是一个等价的迭代解决方案:

template <typename Iter>
bool next(Iter begin, Iter end)
{
    while (begin != end)       // we're not done yet
    {
        --end;
        if ((*end & 1) == 0)   // even number is treated as zero
        {
            ++*end;            // increase to one
            return true;       // still more numbers to come
        }
        else                   // odd number is treated as one
        {
            --*end;            // decrease to zero and loop
        }
    }
    return false;              // that was the last number
}

Answer 2

这些问题在功能上很容易解决.要找到长度为n的解,首先找到长度为n-1的解,然后将"0"和"1"附加到这些解,使解空间加倍.

这是一个简单的递归Haskell程序:

comb 0 = [[]]

comb n =
    let rest = comb (n-1)
    in  map ('0':) rest
     ++ map ('1':) rest

这是一个测试运行:

> comb 3
["000","001","010","011","100","101","110","111"]