Derangements¶
AUTHORS:
- Alasdair McAndrew (2010-05): Initial version
- Travis Scrimshaw (2013-03-30): Put derangements into category framework
-
class
sage.combinat.derangements.
Derangement
(parent, *args, **kwds)¶ Bases:
sage.combinat.combinat.CombinatorialElement
A derangement.
A derangement on a set
is a permutation
such that
for all
, i.e.
is a permutation of
with no fixed points.
EXAMPLES:
sage: D = Derangements(4) sage: elt = D([4,3,2,1]) sage: TestSuite(elt).run()
-
to_permutation
()¶ 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]
-
-
class
sage.combinat.derangements.
Derangements
(x)¶ 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:
x
– Can be an integer which corresponds to derangements of, a list, or a string
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]
-
Element
¶ alias of
Derangement
-
cardinality
()¶ 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
-
random_element
()¶ 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() []