算法生成的那些所有可能的阵列给定长度的和零点 [英] Algorithm to generate all possible arrays of ones and zeros of a given length

问题描述

我如何可以生成长度为n位的阵列中所有可能的比特组合。如果我开始与我的数组全零然后有n可能性以放置第一比特和用于这n可能性有n-1的可能性以放置第二个位..单元所有n个比特被设置为1。但到目前为止，我没把它编出来。

How can I generate all possible bit combinations in an array of bits of length n. If I start with all zeros in my array then there are n possibilities to place the first bit and for these n possibilities there are n-1 possibilities to place the second bit.. unit all n bits are set to one. But so far I didn't manage to program it out.

也有许多人指出，我可以从0数到（2 ^ N）-1和打印二进制数做到这一点。这将是一个简单的方法来解决这个问题，但是在这种情况下，我只是让机器计数告诉它在什么地方的人，而不是。我这样做的学习，所以我想知道如何编程出来的人，配售的方式。

Also many people pointed out that I can do this by counting from 0 to (2^n)-1 and printing the number in binary. This would be an easy way to solve the problem, however in this case I just let the machine counting instead of telling it where to place ones. I do this for learning, so I would like to know how to program out the ones-placing approach.

推荐答案

你会如何手动指望在纸上？你会检查最后一个数字。如果是0，将其设置为1。如果已经是1，你把它设置回0，继续下一个数字。所以这是一个递归过程。

How would you count manually on paper? You would check the last digit. If it is 0, you set it to 1. If it is already 1, you set it back to 0 and continue with the next digit. So it's a recursive process.

下面的程序通过突变序列产生所有可能的组合：

The following program generates all possible combinations by mutating a sequence:

#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数组载体中。让我们用一个字符串矢量：

The program works with any sequence of any type. If you need all possible combinations at the same time, just put them into a collection instead of printing them out. Of course you need a different element type, because you cannot put C arrays into a vector. Let's use a vector of strings:

#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
}

如果你不喜欢递归，这里是一个等价迭代求解：

If you don't like recursion, here is an equivalent iterative solution:

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
}

这篇关于算法生成的那些所有可能的阵列给定长度的和零点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！