Permutations with limitations

Question

I've got and interesting problem that I cannot cope with for a some time. We have N letters and N corresponding to them envelopes that means all the letters and envelopes are addressed (with the same permutation). The task is to find the number of possible permutations of the letters that have no fixed points - each letter is in envelope which is differently than this letter addressed. The problem is quite easy when the letters (and envelopes) are addressed by some N-permutation. Then all we have to do is to find the number of N-derangements ( http://en.wikipedia.org/wiki/Derangement ).

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

 5 
 1 1 2 2 3

then the answer is 4, because we have only 4 situations when each letter is in not corresponding envelope and they are:

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

(so we do not distinguish the letters with the same addresses).

For:

6
0 0 0 1 1 1

The answer is 1. Because: 1 1 1 0 0 0 is the only way.

I almost forgot.. 1<=N<=15 is enough.

I'm wondering if is there any way to count it quite quickly and how to do that.

How should I approach with an algorithm?

Answer 1

First attempt, treat it as a straightforward dynamic programming problem.

So you work from left to right, for each position in the list of envelopes, for each possible set of letters you can have left, figure out the number of ways you could get to that point. Moving forward is easy, you just take a set, you know how many ways there are to get there, then for each letter that you could put in the next envelope, you increase the sum of the resulting set by the number of ways there were to get to that point. When you reach the end of the list of envelopes, you'll find how many ways there are to have 0 letters left, which is your answer.

With your second example, that could 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 will get you to about the computational range that you asked for. At 15 you have 2^15 = 32768 possible subsets to keep track of which is very doable. Somewhere around 20 you'll start running out of memory though.

Can we improve this? The answer is that we can. The vast majority of our energy is spent on remembering, say, whether we have used envelopes labeled 8 versus envelopes labeled 9 so far. But we don't care about that. What determines how many ways there are to finish is not whether we used an envelope 8 or 9. But rather the pattern. How many labels are there that have x envelopes and y letters left. Not which labels are which, just how many.

So if we track just that information, at each step we can grab an envelope with a label that has the most envelopes left, and if there is a tie, we'll pick one with the fewest letters left (and if there is still a tie, we really don't care which one we get). And do the calculation as before, but with far fewer intermediate states. (We do not wind up with the envelopes lined up as you have it. But do a stable sort on the final letters with envelopes, and you'll get back the listing you has above.)

Let us use the notation [x y]: z to mean that there are z labels with x envelopes and y letters left. And we have a list of such labels Then your example of 1 1 2 2 3 could be represented as {[2 2]: 2, [1 1]: 1}. And for a transition we'll take one of the [2 2] labels, and either use a letter from the other one (giving us a transition to {[2 1]: 1, [1 2]: 1, [1 1]: 1}) or we'll take one of the [2 2] labels, and use the letter from the [1 1] label (giving us a transition to {[2 2]: 1, [1 2]: 1, [1 0]: 1}).

Let's carry out the calculation. I'll list states, counts of ways to get there, and the transitions you make:

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 a crazy amount of work - far more than enumerating. And it was!

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

Answer 2

15 "normal" permutations would require 1.3*10^9 attempts with brute force, but by using the same keys we have much less permutations left.

Lets use your example: 5 cards with 1 1 2 2 3

Set up a permutation array

5 4 3 2 1

and prepare to iterate through it by decreasing it right to left like a number. Ignore all combinations which 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

Debatably this can be vastly improved with a better permutation algorithm, but this is not easy, I must think over it.

The next step is generating your comparison. The permutation array selects a permutation:

5 4 3 1 2 means 3 2 2 1 1

This will you test for derangement. One thing which will vastly speed up your comparison will be that you can skip invalid combinations.

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

Every time you have found a derangement, increase a counter. Done.