Permutations with some fixed numbers

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?

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

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.

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.

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.