OKlibrary  0.2.1.6
Permutations.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 21.8.2012 (Swansea) */
00002 /* Copyright 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/SymmetricGroups.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/Auxiliary.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00025 
00026 
00027 /* ************
00028    * Counting *
00029    ************
00030 */
00031 
00032 /* The number of permutations of n objects: */
00033 count_permutations(n) := n!$
00034 
00035 
00036 /* ****************************
00037    * Lexicographical ordering *
00038    ****************************
00039 */
00040 
00041 /* Produces a list of all permutations of M (a set or list) in lexicographical
00042    order: */
00043 lex_permutations_l(M) := listify(permutations(M))$
00044 /* This implementation assumes that the internal order of sets is given by
00045    lexicographical order.
00046 */
00047 
00048 /* Returns the rank (position) of the permutation p of [1,...,n] in the
00049    lexicographical enumeration of all permutations, where n = length(p): */
00050 rank_lex_permutations(p) := factoradic2int(inversion_vector_perl(p))+1$
00051 
00052 /* Returns the 'x'th permutation in the lexicographical enumeration of all
00053    permutations of [1,...,n] for 1 <= x <= n!: */
00054 unrank_lex_permutations(x,n) := if n=0 then [] else
00055  perl_inversion_vector(paddingfront_l(0,int2factoradic(x-1),n))$
00056 
00057