带有重复的递归排列 [英] Recursive permutations with repetition

问题描述

我正在尝试编写一个递归函数，该函数通过给定列表的重复获取所有排列.

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

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

我想要此代码的递归版本，以便我可以获得任意大小集合的排列:

I want a recursive version of this code so I can get permutations 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++ {

         perm[0] = S[i];
         perm[1] = S[j];
         perm[2] = S[k];
         permutations.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.

我更喜欢伪代码解决方案，我没有在 C++ 中实现它

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

推荐答案

我认为迭代解决方案会更有效率，并且可以编写为支持任意维度和数量的符号.代码是用 C++ 编写的，但我故意保持简单，以便您可以轻松地翻译成伪代码或其他语言:

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

输出应该是:

AAA BAA CAA DA​​A ABA BBA CBA DBA ACA BCA CCA DCA ADA BDA CDA DDA AABBAB CAB DAB ABB BBB CBB DBB ACB BCB CCB DCB ADB BDB CDB DDB AAC BACCAC DAC ABC BBC CBC DBC ACC BCC CCC DCC ADC BDC CDC DDC AAD BAD CADDAD 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 设为模板函数，并使其适用于 char 以外的其他类型.

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

============ 更新 ==================

============ 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屋！