programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Jeanne Boyarsky
• Tim Cooke
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Mikalai Zaikin
• Carey Brown
Bartenders:

# Deranged permutations

Ranch Hand
Posts: 1296
• Number of slices to send:
Optional 'thank-you' note:
For a 2 element list with 2 distinct elements [0, 1] a permutation exists where there all elements are in a different position than the original list. We can say that the maximum "derangement" of the list is 2

For a 3 element list with 2 distinct elements [0, 1, 1] every permutation has at least one element that is in the same position in the permuted list as the original list. The maximum derangement of this list is also 2.

Is there a formula for the generalization of this observation. i.e. for an M element list with N distinct elements (where N <= M) the maximum possible derangement of a permutation of that list is X?

I've tried googling, but I can't come up with the right keywords, and the math quickly goes over my head.

Marshal
Posts: 28000
94
• Number of slices to send:
Optional 'thank-you' note:
It can't just be a function of M and N, because (up to isomorphism) there are two different 4-element lists with 2 distinct elements, namely [0, 0, 1, 1] and [0, 1, 1, 1].

And they have different maximum derangements: the first's MD is 4 and the second's is 2.

In general for a list with K zeroes and L ones, where K <= L, the maximum derangement is 2K, unless I'm missing something. But extending that to 3 or more distinct elements isn't nearly as obvious, although I haven't spent any time poking at it.

Garrett Rowe
Ranch Hand
Posts: 1296
• Number of slices to send:
Optional 'thank-you' note:

Paul Clapham wrote:It can't just be a function of M and N, because (up to isomorphism) there are two different 4-element lists with 2 distinct elements, namely [0, 0, 1, 1] and [0, 1, 1, 1].

And they have different maximum derangements: the first's MD is 4 and the second's is 2.

Good point. I hadn't thought that through.

In general for a list with K zeroes and L ones, where K <= L, the maximum derangement is 2K, unless I'm missing something. But extending that to 3 or more distinct elements isn't nearly as obvious, although I haven't spent any time poking at it.

Unfortunately the problem I was trying to solve might be a bit more difficult. I was looking at the Best Shuffle problem on Rosetta Code and trying to figure out if there is an algorithm for deciding ahead of time the maximum deraingement of the target word. You could then theoretically continuously random shuffle and check until you came up with a permutation with maximum derangement,

Paul Clapham
Marshal
Posts: 28000
94
• Number of slices to send:
Optional 'thank-you' note:

Garrett Rowe wrote:Unfortunately the problem I was trying to solve might be a bit more difficult.

It might, or it might not. It might depart from the triviality of the case I already analyzed in a linear way, or it might turn out to be more like calculating the number of partitions of an integer. My spidey math sense is leaning towards the latter but I wouldn't bet big money on either outcome at this point in time.

lowercase baba
Posts: 13089
67
• Number of slices to send:
Optional 'thank-you' note:

Garrett Rowe wrote:
For a 3 element list with 2 distinct elements [0, 1, 1] every permutation has at least one element that is in the same position in the permuted list as the original list. The maximum derangement of this list is also 2.

maybe i'm slow...why is the derrangement 2? If there is no permutation where all the elements are different, why wouldn't it be 1?

Paul Clapham
Marshal
Posts: 28000
94
• Number of slices to send:
Optional 'thank-you' note:
Lines 01 and 02 differ in the first two positions, so their "derangement" is two, for example.

fred rosenberger
lowercase baba
Posts: 13089
67
• Number of slices to send:
Optional 'thank-you' note:
ah...thanks. it's not the number of different arrangements with all elements moved, but how many elements are in a different position for each permutation, then the maximum of those...
thanks

 It means our mission is in jeapordy! Quick, read this tiny ad! a bit of art, as a gift, the permaculture playing cards https://gardener-gift.com