在C++中打印所有排列

Question

我想列出所有安排，以下是我的示例代码：

const unsigned char item1[] = {'b'};
const unsigned char item2[] = { 'A', 'C' ,'D'};
const unsigned char item3[] = {'1','2'};

int _tmain(int argc, _TCHAR* argv[])
{
    for (int i = 0; i < sizeof(item1) / sizeof(unsigned char); i++){
        for (int j = 0; j < sizeof(item2) / sizeof(unsigned char); j++){
            for (int k = 0; k < sizeof(item3) / sizeof(unsigned char); k++){
                printf("%c%c%c\n",item1[i],item2[j],item3[k]);
            }
        }
    }
    return 0;
}

这将打印所有排列，但我担心如果数组项是从item1到item99，那么代码就很难维护。是否有更好的解决方案来打印所有排列？谢谢！

- Tu Roland

---

我不会说此方法更好，但你需要的可能是一个由向量组成的向量，并且需要使用递归函数处理它。 - Yunnosch

你可以使用 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0])) 来简化数组长度的计算。 - pbn

@Hamed，我不确定你所说的“a couple loops”是什么意思。我理解“a couple of loops”等同于“非常少的循环”。OP的“item1”到“item99”似乎是在谈论需要通过100个循环来处理100个项目，即使转换为向量的向量也是适用的。我可能误解了你的意思。请随意详细说明。 - Yunnosch

@Hamed，他需要展示所有的组合，当n=100时，有1000000种组合，对于三个数组，需要三个循环语句。 - Swift - Friday Pie

如果你想对每个数组处理2个项目，并且有100个不同的数组，那么请做好等待的准备。如果平均循环持续时间为1纳秒，则所需总时间约为400亿年，大约比宇宙存在的时间长4倍... - Mats Petersson

Answer 1

你可以将“迭代器”存储在向量中，然后可以执行以下操作：

bool increase(const std::vector<std::string>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] == v[index].size()) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

void do_job(const std::vector<std::string>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = v.size(); i != size; ++i) {
        std::cout << v[i][it[i]];
    }
    std::cout << std::endl;
}

void iterate(const std::vector<std::string>& v)
{
    std::vector<std::size_t> it(v.size(), 0);

    do {
        do_job(v, it);
    } while (increase(v, it));
}

演示

- Jarod42

Answer 2

一种不错的解决方法是将问题视为整数基转换问题。因此，所有数组大小的乘积是组合的总数。输出字符串 n 就足以确定应在字符串中打印的数组索引。 既然您已经将其标记为 C++ 问题，我会使用 2-D 向量，因为这样可以使生活变得更加简单：

int _tmain(int argc, _TCHAR* argv[])
{
    // Initialize the vector
    vector<vector<char>> v( 3 );

    v[0].push_back( 'b' );
    v[1].push_back( 'A' );
    v[1].push_back( 'C' );
    v[1].push_back( 'D' );
    v[2].push_back( '1' );
    v[2].push_back( '2' );

    // This is a convenience vector of sizes of each 1-D vector
    vector<size_t> sizes( v.size() );

    // Get the total number of combinations and individual vector
    // sizes
    size_t total = 1;
    for( size_t i = 0; i < v.size(); ++i )
    {
        sizes[i] = v[i].size();
        total *= sizes[i];
    }

    size_t done = 0;

    // Loop till all the combinations are printed
    while( done != total )
    {
        // Remainder, which is the index of the element
        // in the 1-D vector that is to be printed
        size_t r = 0;
        // Quotient to be used for the next remainder
        size_t q = done;
        // Combination to be printed
        string s = "";

        // Loop over the 1-D vectors, picking the correct
        // character from each
        for( size_t i = 0; i < v.size(); ++i )
        {
            r = q % sizes[v.size() - 1 - i];
            q = static_cast<size_t>( floor( q/sizes[v.size() - 1 - i] ) );
            s = v[v.size() - 1 - i][r] + s;
        }

        cout<<s<<"\n";

        done++;
    }
    return 0;
}

- mahesh

---

_tmain() 是特定于操作系统的。它不是标准C++。 - Peter

没有关系，就是它不会影响逻辑。我只是使用了原帖作者的设定。 - mahesh

@TuRoland：我在Linux上尝试过，它确实可以工作。它在哪个阶段崩溃了？ - mahesh

@TuRoland：抱歉，代码有一点小差异。我复制粘贴了一个旧版本。现在已经编辑过答案了。 - mahesh