Recursive algorithm to get combinations of string in particular order

Question

There are several algorithms out there that print all combinations of a string, but I need one that prints them out in a specific order. Currently I am using a standard permutation algorithm similar to the one in the top answer (not the question itself) of this question: C++ recursive permutation algorithm for strings -> not skipping duplicates

For example, for the input "ABC", the output will be: ABC ACB BAC BCA CAB CBA

For the input "ACC", it will be: ACC CAC CCA

The outputs are all correct, however I need them in a different order. The input will only consist of the characters 'A' and 'C', and I am sorting the string alphabetically before inputting it to the recursive function for convenience so the input string will always have the same characters together (i.e. AACCC). As for the order, I want to treat the collection of 'C's as a single entity which I shift left for each set of permutations of the characters to the right of the first 'C' only. So for input "ACC", the first output is "ACC" which is OK, the next output should be "CCA" because I shifted all the 'C's one step to the left, then the permutations of "CCA" of all the characters to the right of the first 'C' is the final output which is just "ACA".

I need it to look like this for these inputs:

Input: ACC

Output: ACC CCA CAC

Input: AACC

Output:

AACC ACCA ACAC CCAA CACA CAAC

Any idea how I should modify my algorithm to produce the combinations in this order?

The description is a bit confusing. Could you show the correct output for AABBCC? — Eric Mickelsen
I will only ever use it for a string consisting of just two kinds of characters, so assume it consists of just A's and C's but no B's. — Mark Skinner
you still need to clarify the output order you want. it's ambiguous or confusing. my advice is to generate all the permutations, then apply a sorting function on these results that guarantees the order you want. not only will the be more straightforward, but will make sure you fully define the desired output order (by writing the comparison function for the sort) — davec
First of all the results are given by the binomial combination n!/( n!*( n! - k!) ). For example if the input are 3 letters and 2 are the same letter the result is ( 3 2 ) or 3! /( 3! * ( 3! - 2! ) ) = 3, that's why you have 3 outputs in that case — Alberto Bonsanto
So I should build an array using a recursive function, and pass it as a parameter? But wouldn't that cause a stack overflow quickly for larger inputs? — Mark Skinner

Eric Mickelsen Eric Mickelsen · Accepted Answer · 2012-11-10T22:00:02

For a string with two distinct characters A and C, given n is the number of A's, it sounds like what you're looking for is a concatenation of these sequences: All permutations beginning with exactly n A's in reverse lexicographic order, all permutations beginning with exactly n-1 A's in reverse lexicographic order, etc. So, you could take your existing output which is in lexicographic order, and iterate over it in reverse order, selecting elements matching /^A{n}C/, /^A{n-1}C/ through /^A{0}C/ and adding them to a new collection.

You could generate this output directly by generating strings of A's of each length from n A's to zero and then for each one, append the permutations of the remaining characters in reverse lexicographic order.

Recursive algorithm to get combinations of string in particular order

1 Answers