Constrained permutations

Question

I have an interesting problem that I can’t deal with for a while. We have N letters and N envelopes corresponding to them, which means that all letters and envelopes are addressed (with the same permutation). The task is to find the number of possible permutations of letters that do not have fixed points - each letter is in an envelope that differs from this letter. The problem is quite simple when the letters (and envelopes) are addressed by some N-permutation. Then we only need to find the number of N-disorders ( http://en.wikipedia.org/wiki/Derangement ).

But this problem can be much more interesting in general. We are assigned the number N and N numbers - the i-th number indicates the address for the i-th letter (and envelope). The first number is 0 (so we have letters and envelopes with the number [0, ..., N-1]). Then how many violations do we have? For example, we give:

5 1 1 2 2 3 

then the answer is 4, because we have only 4 situations where each letter is in a non-corresponding envelope, and they:

 2 2 1 3 1 2 2 3 1 1 2 3 1 1 2 3 2 1 1 2 

(therefore we do not distinguish letters with identical addresses).

For:

 6 0 0 0 1 1 1 

Answer: 1. Because: 1 1 1 0 0 0 is the only way.

I almost forgot .. 1 <= N <= 15. Enough.

I am wondering if there is a way to figure this out pretty quickly and how to do it.

How do I approach with the algorithm?

Answer 1

The first attempt is to consider it as a problem of direct dynamic programming.

So, you work from left to right, for each position in the list of envelopes, for each possible set of letters that you can leave, find out the number of ways you could get to this point. Moving forward is easy, you just take the set, you know how many ways to get there, and then for each letter you could add to the next envelope, you increase the sum of the result set by the number of ways to get to this point. When you get to the end of the list of envelopes, you will find how many 0 letters you have left, which is your answer.

In your second example, this may progress as follows:

 Step 0: next envelope 1 {1: 2, 2: 2, 3: 1}: 1 -> {1: 2, 2: 1, 3: 1} -> {1: 2, 2: 2} Step 1: next envelope 1 {1: 2, 2: 1, 3: 1}: 1 -> {1: 2, 2: 1} -> {1: 2, 3: 1} {1: 2, 2: 2}: 1 -> {1: 2, 2: 1} Step 2: next envelope 2 {1: 2, 2: 1}: 2 -> {1: 1, 2: 1} {1: 2, 3: 1}: 1 -> {1: 1, 3: 1} -> {1: 2} Step 3: next envelope 2 {1: 1, 2: 1}: 2 -> {2: 1} {1: 1, 3: 1}: 1 -> {1: 1} -> {3: 1} {1: 2}: 1 -> {1: 1} Step 4: next envelope 3 {2: 1}: 2 -> {} {1: 1}: 2 -> {} {3: 1}: 1 // Dead end. Step 5: {}: 4 

This works, and you get acquainted with the request for the computational range. At 15, you have 2 ^ 15 = 32768 possible subsets to keep track of, which is very convenient. Somewhere around 20 you will start running out of memory.

Can we improve this? The answer is that we can. The vast majority of our energy is spent remembering, say, whether we used envelopes labeled 8 or envelopes labeled as 9. But we don’t care. What determines how many ways to finish is not whether we used envelope 8 or 9. But rather a sample. How many labels are there that have envelopes x and letters y. Not the tags that how much.

So, if we track only this information, at each step we can grab an envelope with a label with more envelopes left, and if there is a tie, we will choose one with the fewest letters on the left (and if it still remains a tie, we don’t care which one we get). And do the calculations as before, but with much fewer intermediate states. (We do not complete the envelopes, are lined up as you have, but do a stable look on the final letters with envelopes, and you will return the list that you have above.)

We use the notation [xy]: z to denote z marks with x envelopes and y letters on the left. And we have a list of such tags. Then your example 1 1 2 2 3 can be represented as {[2 2]: 2, [1 1]: 1} . And for the transition, we will take one of the labels [2 2] and either use the letter from the other (give us the transition to {[2 1]: 1, [1 2]: 1, [1 1]: 1} ), or we will take one of the labels [2 2] and use the letter from the label [1 1] (giving us the transition to {[2 2]: 1, [1 2]: 1, [1 0]: 1} ).

Carry out a calculation. I will list the states, the number of ways to get there and the transitions you made:

 Step 1: {[2 2]: 2, [1 1]: 1}: 1 -> 1 * {[2 1]: 1, [1 2]: 1, [1 1]: 1} -> 1 * {[2 2]: 1, [1 2]: 1, [1 0]: 1} Step 2: {[2 1]: 1, [1 2]: 1, [1 1]: 1}: 1 -> 1 * {[1 1]: 3} -> 1 * {[1 1]: 1, [1 2]: 1, [1 0]: 1} {[2 2]: 1, [1 2]: 1, [1 0]: 1}: 1 -> 1 * {[1 2]: 1, [1 1]: 1, [1 0]: 1} Step 3: {[1 1]: 3}: 1 // This is 2x because once the label is chosen, there are 2 letters to use. -> 2 * {[0 1]: 1, [1 0]: 1, [1 1]: 1} {[1 1]: 1, [1 2]: 1, [1 0]: 1}: 2 -> 1 * {[1 0]: 1, [1 2]: 1, [0 0]: 1} -> 1 * {[1 1]: 2, [0 0]: 1} {[1 2]: 1, [1 1]: 1, [1 0]: 1}: 1 -> 1 * {[1 1]: 2, [0 0]: 1} -> 1 * {[1 2]: 1, [1 0]: 1, [0 0]: 1} Step 4: {[0 1]: 1, [1 0]: 1, [1 1]: 1}: 2 -> 1 * {[1 1]: 1, [0 0]: 2} -> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1} {[1 0]: 1, [1 2]: 1, [0 0]: 1}: 2 -> 1 * {[1 1]: 1, [0 0]: 2} {[1 1]: 2, [0 0]: 1}: 2 -> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1} Step 5: {[1 1]: 1, [0 0]: 2}: 4 // dead end {[1 0]: 1, [0 1]: 1, [0 0]: 1}: 4 -> 1 * {[0 0]: 3} 

So the answer is 4.

This may seem like an insane amount of work - much more than an enumeration. And it was!

However, it scales. Try it with 100 letters and envelopes and it should run fast.

Answer 2

15 "normal" permutations will require attempts of 1.3 * 10 ^ 9 with brute force, but with the same keys we have much fewer permutations left.

Let's use your example: 5 cards with 1 1 2 2 3

Set up an array of permutations

5 4 3 2 1

and get ready to iterate through it, decreasing it from right to left as a number. Ignore all combinations that are not permutations.

5 4 3 2 1 ignore

5 4 3 2 0 ignore

5 4 3 1 5 ignore

...

5 4 3 1 2 ok

It is unlikely that this can be significantly improved with a better permutation algorithm, but it is not easy, I should think about it.

The next step is your comparison. The permutation array selects the permutation:

5 4 3 1 2 means 3 2 2 1 1

You will experience this disorder. One thing that will greatly speed up your comparison will be that you can skip invalid combinations.

If 5 at the beginning selects the wrong item, you can skip all 5 XXXX and continue with 4 5 3 2 1.

Each time you find an upset, increase the counter. Done.