AUTHORS:
Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element
A derangement.
A derangement on a set is a permutation
such that
for all
, i.e.
is a permutation of
with no
fixed points.
Return the permutation corresponding to self.
EXAMPLES:
sage: D = Derangements(4)
sage: p = D([4,3,2,1]).to_permutation(); p
[4, 3, 2, 1]
sage: type(p)
<class 'sage.combinat.permutation.StandardPermutations_all_with_category.element_class'>
sage: D = Derangements([1, 3, 3, 4])
sage: D[0].to_permutation()
Traceback (most recent call last):
...
ValueError: Can only convert to a permutation for derangements of [1, 2, ..., n]
Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation
The class of all derangements of a set or multiset.
A derangement on a set is a permutation
such that
for all
, i.e.
is a permutation of
with no
fixed points.
For an integer, or a list or string with all elements distinct, the derangements are obtained by a standard result described in [DerUB]. For a list or string with repeated elements, the derangements are formed by computing all permutations of the input and discarding all non-derangements.
INPUT:
REFERENCES:
[DerUB] | http://www.u-bourgogne.fr/LE2I/jl.baril/derange.pdf |
EXAMPLES:
sage: D1 = Derangements([2,3,4,5])
sage: D1.list()
[[3, 4, 5, 2],
[5, 4, 2, 3],
[3, 5, 2, 4],
[4, 5, 3, 2],
[4, 2, 5, 3],
[5, 2, 3, 4],
[5, 4, 3, 2],
[4, 5, 2, 3],
[3, 2, 5, 4]]
sage: D1.cardinality()
9
sage: D1.random_element() # random
[4, 2, 5, 3]
sage: D2 = Derangements([1,2,3,1,2,3])
sage: D2.cardinality()
10
sage: D2.list()
[[2, 1, 1, 3, 3, 2],
[2, 1, 2, 3, 3, 1],
[2, 3, 1, 2, 3, 1],
[2, 3, 1, 3, 1, 2],
[2, 3, 2, 3, 1, 1],
[3, 1, 1, 2, 3, 2],
[3, 1, 2, 2, 3, 1],
[3, 1, 2, 3, 1, 2],
[3, 3, 1, 2, 1, 2],
[3, 3, 2, 2, 1, 1]]
sage: D2.random_element() # random
[2, 3, 1, 3, 1, 2]
alias of Derangement
Counts the number of derangements of a positive integer, a
list, or a string. The list or string may contain repeated
elements. If an integer is given, the the value returned
is the number of derangements of
.
For an integer, or a list or string with all elements
distinct, the value is obtained by the standard result
.
For a list or string with repeated elements, the number of
derangements is computed by Macmahon’s theorem. If the numbers
of repeated elements are then the number
of derangements is given by the coefficient of
in the expansion of
where
.
EXAMPLES:
sage: D = Derangements(5)
sage: D.cardinality()
44
sage: D = Derangements([1,44,918,67,254])
sage: D.cardinality()
44
sage: D = Derangements(['A','AT','CAT','CATS','CARTS'])
sage: D.cardinality()
44
sage: D = Derangements('UNCOPYRIGHTABLE')
sage: D.cardinality()
481066515734
sage: D = Derangements([1,1,2,2,3,3])
sage: D.cardinality()
10
sage: D = Derangements('SATTAS')
sage: D.cardinality()
10
sage: D = Derangements([1,1,2,2,2])
sage: D.cardinality()
0
Produces all derangements of a positive integer, a list, or
a string. The list or string may contain repeated elements.
If an integer is given, then a random
derangements of
is returned
For an integer, or a list or string with all elements distinct, the value is obtained by an algorithm described in [Martinez08]. For a list or string with repeated elements the derangement is formed by choosing an element at random from the list of all possible derangements.
OUTPUT:
A single list or string containing a derangement, or an empty list if there are no derangements.
REFERENCES:
[Martinez08] | http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf |
EXAMPLES:
sage: D = Derangements(4)
sage: D.random_element() # random
[2, 3, 4, 1]
sage: D = Derangements(['A','AT','CAT','CATS','CARTS','CARETS'])
sage: D.random_element() # random
['AT', 'CARTS', 'A', 'CAT', 'CARETS', 'CATS']
sage: D = Derangements('UNCOPYRIGHTABLE')
sage: D.random_element() # random
['C', 'U', 'I', 'H', 'O', 'G', 'N', 'B', 'E', 'L', 'A', 'R', 'P', 'Y', 'T']
sage: D = Derangements([1,1,1,1,2,2,2,2,3,3,3,3])
sage: D.random_element() # random
[3, 2, 2, 3, 1, 3, 1, 3, 2, 1, 1, 2]
sage: D = Derangements('ESSENCES')
sage: D.random_element() # random
['N', 'E', 'E', 'C', 'S', 'S', 'S', 'E']
sage: D = Derangements([1,1,2,2,2])
sage: D.random_element()
[]