how to find Derangement of a multiset

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

how to find Derangement of a multiset

Post by rushel »

can anybody give me a link or any combinatorics formula or any algorithm of
number of derangement of a multiset.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Just to clarify, what do you understand under "derangement"?

For permutations, derangement is a permutation without fixed points. The best definition I could come up with for multisets:

Suppose M is a multiset. Let sorted(M) be the vector containing all elements of M in sorted order.

For example, if M = {3, 4, 2, 3, 1}, then sorted(M) = (1,2,3,3,4).

Let isPermutation(V,M) be true if and only if the vector V contains exactly the elements of M, in any order.

For example:
isPermutation( (1,3,2), {1,2,3} ) = true
isPermutation( (1,3,2,3), {1,2,3} ) = false

Then, a derangement of M is a vector V such that isPermutation(V,M) && (V and sorted(M) differ on all places).

For example, for M = {3, 4, 2, 3, 1} the vector (3,3,1,4,2) is a derangement, and the vector (4,1,3,2,3) is not.

Is this what you want?

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel »

misof, yes thats is the thing i want . sorry for my late reply.

Post Reply

Return to “Algorithms”