递归组合 [英] Recursive combinations

问题描述

我想写一个递归函数获取给定列表中的所有组合。

I'm trying to write a recursive function that gets all combinations of a given list.

Eg. set = ABC
1. AAA
2. AAB
3. AAC
4. ABA 
N. CCC

我想这code递归版本，这样我就可以得到组合集的任何尺寸的：

I want a recursive version of this code so I can get combinations for sets of any size:

for i=0; i<S.size(); i++ {
   for j=0; j<S.size(); j++ {
      for k=0; k<S.size(); k++ {

         combo[0] = S[i];
         combo[1] = S[j];
         combo[2] = S[k];
         combinations.push(combo);

      }
   }
}

我有一些麻烦缠绕我的头周围的问题。到目前为止，我想我需要找到我的时候已经达到了一个任意深度停止再咒骂。

I'm having some trouble wrapping my head around the problem. So far I'm thinking I need to find when I've reached an arbitrary depth to stop re-cursing.

编辑：我想preFER一个伪code的解决方案，我不是在C执行这一++

I'd prefer a pseudo-code solution, I'm not implementing this in C++

推荐答案

我觉得一个迭代的解决方案将更有效率，而且可以写入支持任意尺寸和符号的数字。在code是C ++，但我delibaretely保持简单，让您可以轻松地转化为伪code或其他语言的：

I think an iterative solution will be more efficient, and it can be written to support arbitrary dimensions and numbers of symbols. The code is in C++, but I delibaretely kept it simple so that you can easily translate into pseudocode or other language:

#include <vector>
#include <cassert>
#include <iostream>

void generate_combinations(const std::vector<char>& symbols, const unsigned int dimension, std::vector<std::vector<char> >& output)
{
    assert( symbols.size() ); // terminate the program if condition not met
    std::vector<char> current_output(dimension);
    std::vector<unsigned int> current_combo(dimension + 1, 0);
    const unsigned int max_symbol_idx = symbols.size() - 1;
    size_t current_index = 0;
    while (current_combo.back() == 0) {
        // add current combination
        for (unsigned int i = 0; i < dimension; ++i) {
            current_output[i] = symbols[current_combo[i]];
        }
        output.push_back(current_output);

        // move to next combination
        while (current_index <= dimension && current_combo[current_index] == max_symbol_idx) {
            current_combo[current_index] = 0;
            ++current_index;
        }
        if (current_index <= dimension) {
            ++current_combo[current_index];
        }
        current_index = 0;
    }
}

int main()
{
    const unsigned int dimension = 3;
    std::vector<char> symbols(4);   
    symbols[0] = 'A';
    symbols[1] = 'B';
    symbols[2] = 'C';
    symbols[3] = 'D';
    std::vector<std::vector<char> > output;
    generate_combinations(symbols, dimension, output);
    for (unsigned int i = 0; i < output.size(); ++i) {
        for (unsigned int j = 0; j < dimension; ++j) {
            std::cout << output[i][j]; // write symbol to standard output
        }
        std::cout << std::endl; // write new line character
    }
}

输出应该是：

The output should be:

AAA BAA CAA DA​​A ABA BBA CBA DBA ACA BCA CCA DCA ADA BDA CDA DDA AAB   BAB CAB DAB ABB BBB CBB DBB ACB BCB建行DCB亚行BDB CDB DDB AAC BAC   CAC DAC ABC广播公司CBC DBC ACC BCC CCC DCC ADC BDC CDC DDC AAD BAD CAD   DAD ABD BBD CBD DBD ACD BCD CCD DCD ADD BDD CDD DDD

AAA BAA CAA DAA ABA BBA CBA DBA ACA BCA CCA DCA ADA BDA CDA DDA AAB BAB CAB DAB ABB BBB CBB DBB ACB BCB CCB DCB ADB BDB CDB DDB AAC BAC CAC DAC ABC BBC CBC DBC ACC BCC CCC DCC ADC BDC CDC DDC AAD BAD CAD DAD ABD BBD CBD DBD ACD BCD CCD DCD ADD BDD CDD DDD

如果要在最后位置的符号，以最快的改变，只是反转所生成的输出的每一行的内容。

If you want the symbols in the last position to change fastest, just reverse the contents of each row of the generated output.

当然，你可以让 generate_combinations 模板功能，使其与其他类型的工作比字符。

Of course, you can make generate_combinations a template function and make it work with other types than char.

============ UPDATE =================

============ UPDATE =================

一个递归的解决方案，当然，更优雅：

A recursive solution is, of course, more elegant:

void add_next_symbol(const std::vector<char>& symbols, const unsigned int dimension, std::vector<char>& current_output, std::vector<std::vector<char> >& output)
{
    if (dimension == 0) {
        output.push_back(current_output);
    } else {
        for (unsigned int i = 0; i < symbols.size(); ++i) {
            current_output.push_back(symbols[i]);
            add_next_symbol(symbols, dimension - 1, current_output, output);
            current_output.pop_back();
        }
    }
}

void generate_combinations_recursive(const std::vector<char>& symbols, const unsigned int dimension, std::vector<std::vector<char> >& output)
{
    std::vector<char> current_output;
    add_next_symbol(symbols, dimension, current_output, output);
}

使用它来代替 generate_combinations 中的第一个程序的功能。它应该给你相同的输出和以前一样。

Use it in place of generate_combinations function in the first program. It should give you the same output as before.

这篇关于递归组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！