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

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

您将如何在纸上手动计数？您将检查最后一位数字。如果为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}