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,