部分排列 [英] Partial permutations

问题描述

我具有以下用于输出部分组合的递归函数:

I have the following recursive function for outputting partial combinations:

void comb(string sofar, string rest, int n) {

    string substring;

    if (n == 0)
        cout << sofar << endl;
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

这样称呼:

comb("", "abcde", 3);

通过部分组合，我的意思是它使用了n个选择和r个元素(而不是n个选择，n个元素).

By partial combinations, I mean that it uses n choices and r elements (rather than n choices, n elements).

但是，我想考虑元素的顺序(即排列).我可以找到很多用于完整排列而并非局部排列的算法.

However, I would like to take the order of elements into account (i.e. permutations). I can find many algorithms for full permutations, but not partial.

推荐答案

您想要排列，因此您应该在substring中的i之后和AND 之前捕获字符:

You want permutations, so you should capture characters before AND after i in substring:

substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());

coliru :

#include <iostream>
#include <string>

using std::string;
using std::cout;

void comb(string sofar, string rest, int n)
{
    // std::cout << "comb('" << sofar << "', '" << rest << "', " << n << ")\n";
    string substring;

    if (n == 0)
        cout << sofar << '\n';
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

int main()
{
    comb("", "abcde", 3);
}

输出(重新格式化):

abc abd abe acb acd ace adb adc ade aeb aec aed
bac bad bae bca bcd bce bda bdc bde bea bec bed
cab cad cae cba cbd cbe cda cdb cde cea ceb ced
dab dac dae dba dbc dbe dca dcb dce dea deb dec
eab eac ead eba ebc ebd eca ecb ecd eda edb edc 

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