Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Derangements
AUTHORS:
- Alasdair McAndrew (2010-05): Initial version - Travis Scrimshaw (2013-03-30): Put derangements into category framework """
#***************************************************************************** # Copyright (C) 2010 Alasdair McAndrew <amca01@gmail.com>, # 2013 Travis Scrimshaw <tscrim@ucdavis.edu> # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #***************************************************************************** from six.moves import range
from sage.structure.parent import Parent from sage.structure.unique_representation import UniqueRepresentation from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets from sage.misc.all import prod from sage.misc.prandom import random, randint from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.rings.all import ZZ, QQ from sage.rings.integer import Integer from sage.combinat.combinat import CombinatorialElement from sage.combinat.permutation import Permutation, Permutations
class Derangement(CombinatorialElement): r""" A derangement.
A derangement on a set `S` is a permutation `\sigma` such that `\sigma(x) \neq x` for all `x \in S`, i.e. `\sigma` is a permutation of `S` with no fixed points.
EXAMPLES::
sage: D = Derangements(4) sage: elt = D([4,3,2,1]) sage: TestSuite(elt).run() """ def to_permutation(self): """ 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 Derangements(UniqueRepresentation, Parent): r""" The class of all derangements of a set or multiset.
A derangement on a set `S` is a permutation `\sigma` such that `\sigma(x) \neq x` for all `x \in S`, i.e. `\sigma` is a permutation of `S` 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 `\{1, 2, 3, \ldots, x\}`, a list, or a string
REFERENCES:
.. [DerUB] http://www.u-bourgogne.fr/LE2I/jl.baril/derange.pdf
- :wikipedia:`Derangement`
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] """ @staticmethod def __classcall_private__(cls, x): """ Normalize ``x`` to ensure a unique representation.
EXAMPLES::
sage: D = Derangements(4) sage: D2 = Derangements([1, 2, 3, 4]) sage: D3 = Derangements((1, 2, 3, 4)) sage: D is D2 True sage: D is D3 True """
def __init__(self, x): """ Initalize ``self``.
EXAMPLES::
sage: D = Derangements(4) sage: TestSuite(D).run() sage: D = Derangements('abcd') sage: TestSuite(D).run() sage: D = Derangements([2, 2, 1, 1]) sage: TestSuite(D).run() """
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: Derangements(4) Derangements of the set [1, 2, 3, 4] sage: Derangements('abcd') Derangements of the set ['a', 'b', 'c', 'd'] sage: Derangements([2,2,1,1]) Derangements of the multiset [2, 2, 1, 1] """
def _element_constructor_(self, der): """ Construct an element of ``self`` from ``der``.
EXAMPLES::
sage: D = Derangements(4) sage: elt = D([3,1,4,2]); elt [3, 1, 4, 2] sage: elt.parent() is D True """ if der.parent() is self: return der raise ValueError("Cannot convert %s to an element of %s"%(der, self))
Element = Derangement
def __iter__(self): """ Iterate through ``self``.
EXAMPLES::
sage: D = Derangements(4) sage: D.list() # indirect doctest [[2, 3, 4, 1], [4, 3, 1, 2], [2, 4, 1, 3], [3, 4, 2, 1], [3, 1, 4, 2], [4, 1, 2, 3], [4, 3, 2, 1], [3, 4, 1, 2], [2, 1, 4, 3]] sage: D = Derangements([1,44,918,67]) sage: D.list() [[44, 918, 67, 1], [67, 918, 1, 44], [44, 67, 1, 918], [918, 67, 44, 1], [918, 1, 67, 44], [67, 1, 44, 918], [67, 918, 44, 1], [918, 67, 1, 44], [44, 1, 67, 918]] sage: D = Derangements(['A','AT','CAT','CATS']) sage: D.list() [['AT', 'CAT', 'CATS', 'A'], ['CATS', 'CAT', 'A', 'AT'], ['AT', 'CATS', 'A', 'CAT'], ['CAT', 'CATS', 'AT', 'A'], ['CAT', 'A', 'CATS', 'AT'], ['CATS', 'A', 'AT', 'CAT'], ['CATS', 'CAT', 'AT', 'A'], ['CAT', 'CATS', 'A', 'AT'], ['AT', 'A', 'CATS', 'CAT']] sage: D = Derangements('CART') sage: D.list() [['A', 'R', 'T', 'C'], ['T', 'R', 'C', 'A'], ['A', 'T', 'C', 'R'], ['R', 'T', 'A', 'C'], ['R', 'C', 'T', 'A'], ['T', 'C', 'A', 'R'], ['T', 'R', 'A', 'C'], ['R', 'T', 'C', 'A'], ['A', 'C', 'T', 'R']] sage: D = Derangements([1,1,2,2,3,3]) sage: D.list() [[2, 2, 3, 3, 1, 1], [2, 3, 1, 3, 1, 2], [2, 3, 1, 3, 2, 1], [2, 3, 3, 1, 1, 2], [2, 3, 3, 1, 2, 1], [3, 2, 1, 3, 1, 2], [3, 2, 1, 3, 2, 1], [3, 2, 3, 1, 1, 2], [3, 2, 3, 1, 2, 1], [3, 3, 1, 1, 2, 2]] sage: D = Derangements('SATTAS') sage: D.list() [['A', 'S', 'S', 'A', 'T', 'T'], ['A', 'S', 'A', 'S', 'T', 'T'], ['A', 'T', 'S', 'S', 'T', 'A'], ['A', 'T', 'S', 'A', 'S', 'T'], ['A', 'T', 'A', 'S', 'S', 'T'], ['T', 'S', 'S', 'A', 'T', 'A'], ['T', 'S', 'A', 'S', 'T', 'A'], ['T', 'S', 'A', 'A', 'S', 'T'], ['T', 'T', 'S', 'A', 'S', 'A'], ['T', 'T', 'A', 'S', 'S', 'A']] sage: D = Derangements([1,1,2,2,2]) sage: D.list() [] """ else:
def _iter_der(self, n): r""" Iterate through all derangements of the list `[1, 2, 3, \ldots, n]` using the method given in [DerUB]_.
EXAMPLES::
sage: D = Derangements(4) sage: list(D._iter_der(4)) [[2, 3, 4, 1], [4, 3, 1, 2], [2, 4, 1, 3], [3, 4, 2, 1], [3, 1, 4, 2], [4, 1, 2, 3], [4, 3, 2, 1], [3, 4, 1, 2], [2, 1, 4, 3]] """ return
def _fixed_point(self, a): """ Return ``True`` if ``a`` has a point in common with ``self._set``.
EXAMPLES::
sage: D = Derangements(5) sage: D._fixed_point([3,1,2,5,4]) False sage: D._fixed_point([5,4,3,2,1]) True """
def _count_der(self, n): """ Count the number of derangements of `n` using the recursion `D_2 = 1, D_3 = 2, D_n = (n-1) (D_{n-1} + D_{n-2})`.
EXAMPLES::
sage: D = Derangements(5) sage: D._count_der(2) 1 sage: D._count_der(3) 2 sage: D._count_der(5) 44 """ # n >= 4
def cardinality(self): r""" 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 `n` is given, the value returned is the number of derangements of `[1, 2, 3, \ldots, n]`.
For an integer, or a list or string with all elements distinct, the value is obtained by the standard result `D_2 = 1, D_3 = 2, D_n = (n-1) (D_{n-1} + D_{n-2})`.
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 `a_1, a_2, \ldots, a_k` then the number of derangements is given by the coefficient of `x_1 x_2 \cdots x_k` in the expansion of `\prod_{i=0}^k (S - s_i)^{a_i}` where `S = x_1 + x_2 + \cdots + x_k`.
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 """
def _rand_der(self): """ Produces a random derangement of `[1, 2, \ldots, n]`.
This is an implementation of the algorithm described by Martinez et. al. in [Martinez08]_.
EXAMPLES::
sage: D = Derangements(4) sage: D._rand_der() [2, 3, 4, 1] """ mark[j-1] = True u -= 1
def random_element(self): r""" Produces all derangements of a positive integer, a list, or a string. The list or string may contain repeated elements. If an integer `n` is given, then a random derangements of `[1, 2, 3, \ldots, n]` 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() [] """
|