[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

combinat::permutations -- permutations

Introduction

The library combinat::permutations provides functions for counting, generating, and manipulating permutations.

Further functions are documented theme by theme in separate help pages:

Details

Categories

Cat::CombinatorialClass

Related Domains

combinat::words

Entries

domtype

The MuPAD domain used to represent permutations: DOM_LIST

typeStandard

The MuPAD type used to represent standard permutations.

Method isA: test if an object is a permutations

Method isAStandard: test if an object is a standard permutations

Method count: number of permutations

Method list: list of the permutations

Method generator: generator for permutations

Method first: first permutation

Method last: last permutation

Method Next: next permutation

Method previous: previous permutation

Method rank: rank of a permutation

Method unrank: permutation unranked

Method random: random permutation

Method inverse: inverse of a standard permutation

Method _mult: Action and composition of permutations

Method toMatrix: permutation matrix of a standard permutation

Example 1

There are 6 permutations of the list [a,b,c]:

>> combinat::permutations::count([a, b, c])
     
                                     6
        

Here is the list:

>> combinat::permutations::list([a, b, c])
     
      [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b],
      
         [c, b, a]]
        

For the permutations of [1,2,3], it is shorter to write:

>> combinat::permutations::count(3);
   combinat::permutations::list(3);
     
                                     6
      
      [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],
      
         [3, 2, 1]]
        

You can use the function combinat::permutations::first to get the ``first'' permutation of a list or the first standard permutation of a given size:

>> combinat::permutations::first([c, b, a, d]);
   combinat::permutations::first(4)
     
                               [a, b, c, d]
      
                               [1, 2, 3, 4]
        

Using combinat::permutations::Next, you can calculate the ``next'' permutation. This function takes as argument the permutation relative to which you want the next one:

>> combinat::permutations::Next([1, 3, 2, 4])
     
                               [1, 3, 4, 2]
        

combinat::permutations::Next returns FAIL when the input is the last permutation:

>> combinat::permutations::Next([4, 3, 2, 1])
     
                                   FAIL
        

You can also go backward with combinat::permutations::last and combinat::permutations::previous

>> combinat::permutations::last([1, 2, 3, 4]);    
   combinat::permutations::previous([1, 3, 2, 4]);    
     
                               [4, 3, 2, 1]
      
                               [1, 2, 4, 3]
        

When you want to run through the permutations of a list, you can generate them one by one to save memory:

>> g := combinat::permutations::generator(3):
   g();
   g(), g(), g(), g(), g(), g();
   h := combinat::permutations::generator([c, a, b]):
   h();
   h(), h(), h(), h(), h(), h();
     
                                 [1, 2, 3]
      
        [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], FAIL
      
                                 [a, b, c]
      
        [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a], FAIL
        

Typically, this would be used as follows:

>> g := combinat::permutations::generator(3):
   while (p := g()) <> FAIL do print(p): end:
     
                                 [1, 2, 3]
      
                                 [1, 3, 2]
      
                                 [2, 1, 3]
      
                                 [2, 3, 1]
      
                                 [3, 1, 2]
      
                                 [3, 2, 1]
        

Example 2

By default, the permutations of a given list are all distinct lists obtained by permuting its elements:

>> combinat::permutations::count([a, a, b]);
   combinat::permutations::list([a, a, b]);
     
                                     3
                                     
                     [[a, a, b], [a, b, a], [b, a, a]]
        

To consider reorderings with multiplicities, one can use the Duplicate option:

>> combinat::permutations::count([a, a, b], Duplicate);
   combinat::permutations::list([a, a, b], Duplicate);
     
                                     6
      
      [[a, a, b], [a, b, a], [a, a, b], [a, b, a], [b, a, a],
      
         [b, a, a]]
        

Note that with the option Duplicateas above, the permutations are not guaranted to be listed in lexicographic order.

Example 3

You can get the rank of a permutation using:

>> combinat::permutations::rank([3, 6, 5, 4, 2, 1]);
     
                                    360
        

Conversely, you can recover the permutation of rank r and size n using:

>> combinat::permutations::unrank(360,6);
     
                            [3, 6, 5, 4, 2, 1]
        

Example 4

Here is the way to get a random permutation:

>> combinat::permutations::random([a,a,b,c,d,d,e,f]);
   combinat::permutations::random(10);
     
                         [d, b, c, f, e, a, d, a]
      
                      [8, 1, 2, 6, 4, 9, 7, 10, 3, 5]
        

Example 5

It is sometime useful to represent a standard permutation by its matrix:

>> combinat::permutations::toMatrix([2, 4, 1, 5, 3]);    
     
                            +-               -+
                            |  0, 0, 1, 0, 0  |
                            |                 |
                            |  1, 0, 0, 0, 0  |
                            |                 |
                            |  0, 0, 0, 0, 1  |
                            |                 |
                            |  0, 1, 0, 0, 0  |
                            |                 |
                            |  0, 0, 0, 1, 0  |
                            +-               -+
        

The inverse permutation is computed by:

>> combinat::permutations::inverse([2, 4, 1, 5, 3])    
     
                              [3, 1, 5, 2, 4]
        

It corresponds to the transpose matrix:

>> combinat::permutations::toMatrix(
      combinat::permutations::inverse([2,4,1, 5, 3])),
   linalg::transpose(
      combinat::permutations::toMatrix([2,4, 1, 5, 3]))
     
                 +-               -+  +-               -+
                 |  0, 1, 0, 0, 0  |  |  0, 1, 0, 0, 0  |
                 |                 |  |                 |
                 |  0, 0, 0, 1, 0  |  |  0, 0, 0, 1, 0  |
                 |                 |  |                 |
                 |  1, 0, 0, 0, 0  |, |  1, 0, 0, 0, 0  |
                 |                 |  |                 |
                 |  0, 0, 0, 0, 1  |  |  0, 0, 0, 0, 1  |
                 |                 |  |                 |
                 |  0, 0, 1, 0, 0  |  |  0, 0, 1, 0, 0  |
                 +-               -+  +-               -+
        

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package