3

How to effectively generate permutations of a number (or chars in word), if i need some char/digit on specified place?

e.g. Generate all numbers with digit 3 at second place from the beginning and digit 1 at second place from the end of the number. Each digit in number has to be unique and you can choose only from digits 1-5.

4 3 2 1 5
4 3 5 1 2
2 3 4 1 5
2 3 5 1 4
5 3 2 1 4
5 3 4 1 2

I know there's a next_permutation function, so i can prepare an array with numbers {4, 2, 5} and post this in cycle to this function, but how to handle the fixed positions?

Radek Simko
  • 15,886
  • 17
  • 69
  • 107

4 Answers4

7

Generate all permutations of 2 4 5 and insert 3 and 1 in your output routine. Just remember the positions were they have to be:

int perm[3] = {2, 4, 5};
const int N = sizeof(perm) / sizeof(int);

std::map<int,int> fixed;  // note: zero-indexed
fixed[1] = 3;
fixed[3] = 1;

do {
    for (int i=0, j=0; i<5; i++)
        if (fixed.find(i) != fixed.end())
            std::cout << " " << fixed[i];
        else
            std::cout << " " << perm[j++];
    std::cout << std::endl;
} while (std::next_permutation(perm, perm + N));

outputs

 2 3 4 1 5
 2 3 5 1 4
 4 3 2 1 5
 4 3 5 1 2
 5 3 2 1 4
 5 3 4 1 2
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
1

I've read the other answers and I believe they are better than mine for your specific problem. However I'm answering in case someone needs a generalized solution to your problem.

I recently needed to generate all permutations of the 3 separate continuous ranges [first1, last1) + [first2, last2) + [first3, last3). This corresponds to your case with all three ranges being of length 1 and separated by only 1 element. In my case the only restriction is that distance(first3, last3) >= distance(first1, last1) + distance(first2, last2) (which I'm sure could be relaxed with more computational expense).

My application was to generate each unique permutation but not its reverse. The code is here:

http://howardhinnant.github.io/combinations.html

And the specific applicable function is combine_discontinuous3 (which creates combinations), and its use in reversible_permutation::operator() which creates the permutations.

This isn't a ready-made packaged solution to your problem. But it is a tool set that could be used to solve generalizations of your problem. Again, for your exact simple problem, I recommend the simpler solutions others have already offered.

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
0

Remember at which places you want your fixed numbers. Remove them from the array. Generate permutations as usual. After every permutation, insert your fixed numbers to the spots where they should appear, and output.

9000
  • 39,899
  • 9
  • 66
  • 104
0

If you have a set of digits {4,3,2,1,5} and you know that 3 and 1 will not be permutated, then you can take them out of the set and just generate a powerset for {4, 2, 5}. All you have to do after that is just insert 1 and 3 in their respective positions for each set in the power set.

I posted a similar question and in there you can see the code for a powerset.

Community
  • 1
  • 1
Kiril
  • 39,672
  • 31
  • 167
  • 226
  • 1
    Generating the powerset takes an exponential amount of memory. Using the standard C++ function `next_permutation`, this can be done with a constant amount of extra memory. – Fred Foo Jan 19 '11 at 21:33
  • @larsmans, I'm a little confused here... I *briefly* looked up a [question in which the powerset is generated using next_permutation](http://stackoverflow.com/questions/3844721/algorithm-to-generate-all-permutation-by-selecting-some-or-all-charaters) and it seems like the the running time is: O(n!*2^n). [Generating a powerset takes O(n*2^n)](http://stackoverflow.com/questions/4630670/time-complexity-of-a-powerset-generating-function), so it seems like you either save on running time or on memory. – Kiril Jan 19 '11 at 23:02
  • First off, the OP's problem is to generate all *permutations*, not *subsets* or *combinations*, so the powerset isn't useful here. Next, the time complexity for generating all permutations is bounded below by the number of permutations which is *n*! = O(*n* ^ *n*). Looping with `next_permutation` is optimal for this problem with time complexity *n*! * O(*n*) = O(*n* ^ (*n* + 1)) = O(*n* ^ *n*) and constant space. – Fred Foo Jan 19 '11 at 23:25