FUNCTION: ListPerm - generate all permutations

CALLING SEQUENCE:

ListPerm(n)

ListPerm(l)

SG[ListPerm](n)

SG[ListPerm](l)

PARAMETERS:

n = any positive integer denoting the degree of a symmetric group

l = any list or set of elements

SYNOPSIS:

• The ListPerm function generates or counts permutations.

• If the first argument is a list or a set l, it generates all distinct permutations of the elements of l.

• If the first argument is an integer, say n, then the function returns the list of all permutations of the symmetric group of degree n.

• ListPerm(n, 'lexic') or ListPerm(n, 'cixel') returns all permutations in lexicographic or reverse lexicographic order.

• ListPerm(n, 'level') returns a list of lists. First list contains all permutations with 0 inversion, second one contains all permutations with 1 inversion, ..., last one contains all permutations with n*(n-1)/2 inversions.

• ListPerm(n, typerm), where typerm is either 'dominant', 'grassmannian' or 'vexillary', returns the list of all dominant, grassmannian or vexillary permutations of the symmetric group of degree n. Vexillary permutations are generated using an algorithm due to J. West.

• When the first argument is an integer, one can use another argument 'code', to produce Lehmer codes instead of permutations. When generating dominant permutations, it is faster to produce codes. One can also add the argument 'nb' to count instead of producing permutations.

• Whenever there is a conflict between the function name ListPerm and another name used in the same session, use the long form SG['ListPerm'].

EXAMPLES:

> with(SG):
> ListPerm([2,2,4]);
 
                      [[2, 2, 4], [2, 4, 2], [4, 2, 2]]
 
> ListPerm(3, 'cixel');
 
     [[3, 2, 1], [2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]
 
> ListPerm(3, 'level');
 
                   [[[1, 2, 3]], [[1, 3, 2], [2, 1, 3]],
 
                    [[3, 1, 2], [2, 3, 1]], [[3, 2, 1]]]
 
> ListPerm(3, 'level', 'code');
 
                   [[[0, 0, 0]], [[0, 1, 0], [1, 0, 0]],
 
                    [[2, 0, 0], [1, 1, 0]], [[2, 1, 0]]]
 
> ListPerm(4, 'vexillary', 'nb');
 
                                  23
 
> ListPerm(5, 'vexillary', 'nb', 'level');
 
                    [1, 4, 6, 11, 16, 18, 18, 15, 9, 4, 1]
 
> ListPerm(5, 'nb', 'level');
 
                    [1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1]