Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 MultisetDerangements

Source Notebook

Find derangements for a multiset

Contributed by: Peter Cullen Burbery

ResourceFunction["MultisetDerangements"][list]

gives the derangements for the multiset list.

ResourceFunction["MultisetDerangements"][list,n]

takes n of the multiset derangements.

ResourceFunction["MultisetDerangements"][n]

represents an operator form that takes n of the multiset derangements.

Details

A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. For example, the only derangements of {1,2,3} are {2,3,1} and {3,1,2}, so !3=2 where !3 is a symbol for derangement.
A multiset is a set with duplicates. DuplicateFreeQ will return False for a multiset. This function finds all the derangements of a multiset, but if two derangements are the same, it deletes them. For example 1234 has the derangment 4321. 1243 is not a derangement because the 1 and 2 have not moved. In the same way 1212 has the derangement 2121. 1221 is not a multiset derangment of 1212 because there is an overlap between the first 12 in 1212 and the first 12 in 1221.

Examples

Basic Examples (1) 

Multiset derangements:

In[1]:=
ResourceFunction["MultisetDerangements"][{1, 2, 3, 2, 1}]
Out[1]=

Scope (2) 

Limit the number returned in a large output:

In[2]:=
ResourceFunction["MultisetDerangements"][{1, 2, 3, 3, 2, 1}]
Out[2]=
In[3]:=
ResourceFunction["MultisetDerangements"][{1, 2, 3, 3, 2, 1}, 3]
Out[3]=

Use an operator form:

In[4]:=
ResourceFunction["MultisetDerangements"][3][{1, 2, 3, 4, 3, 2, 1}]
Out[4]=

Here is an example with the ResourceFunction["Derangements"]:

The resource function Derangements takes the order of the set and does not include multisets in the results:

In[5]:=
ResourceFunction["Derangements"][4]
Out[5]=

MultisetDerangments takes a multiset as input and gives all multiset derangements:

In[6]:=
ResourceFunction["MultisetDerangements"][{1, 2, 1, 2}]
Out[6]=

Publisher

Peter Burbery

Requirements

Wolfram Language 13.3 (June 2023) or above

Version History

  • 1.0.0 – 28 June 2023

Related Resources

Author Notes

There is also a way to do partial derangments, which I am thinking of submitting to the repository. For more information, search for “multiset derangements” on my Wolfram Community Post IntegerDigitsFunction: exploration and examples.

License Information