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?

Improve this question

4 Answers 4

Reset to default
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
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

So I should create next array {0, 2, 4} and use it when putting generated permutations back into the number?
Just put {2,4,5} in the array. I've posted sample code. (Nice exercise ;)
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.

Improve this answer

Comments

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.

Improve this answer

Comments

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.

Improve this answer

3 Comments

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.
@larsmans, I'm a little confused here... I briefly looked up a question in which the powerset is generated using next_permutation and it seems like the the running time is: O(n!*2^n). Generating a powerset takes O(n*2^n), so it seems like you either save on running time or on memory.
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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.