combinat/01 - Sage Wiki

Design discussion for permutations and discrete functions

This is about permutations, and more generally about functions between finite sets.

Desirable features:

(1) Python mantra: an object which looks like a list should behave like a list.

I.e. if the users sees

       sage: p = ...
       sage: p
       [4,1,3,2]

Then he will expect

```
       sage: p[0]
       4
```

(2) The user should be able to manipulate permutations (functions) of

any finite set, and manipulate them as is, without reindexing

       sage: F = Functions([3,4,8])
       sage: F.list()
       [3,3,3]
       [3,3,4]
       [3,3,8]
       ...
       [8,8,8]
       sage: p = F([8,3,4])
       [8,3,4]

In particular, whatever the syntax is, one want to be able to do

       sage: p of 3
       8
       sage: p of 3 = 4
       sage: p
       [4,3,4]

It is important to have short notations for readability of the algorithms. Write access (with surrounding mutability mantra) is necessary as well.

(3) Permutations(n) should be Permutations([1,...,n])

(4) Internally, permutations could be implemented as permutations of

[0...n-1] for speed (future cythonization)
- It's in fact a typical design situation: internal implementations
  using 0...n indexing (cf. matrix, FreeModule, dynkin diagrams, Family, ...) + views on them indexed by whatever is convenient for the user.

(5) Backward compatibility

Potential solutions:

- Current one

      sage: p = DiscreteFunction([3,1,2])
      sage: p[0]
      3
      sage: p[0] = 1; p[1] = 3    # actually not implemented
      sage: p
      [1,3,2]

Caveat: breaks (2)

- Use indexed access starting at 1 (or whatever the smallest letter is)

      sage: p = DiscreteFunction([3,1,2])
      sage: p[1]
      3
      sage: p[1] = 1; p[2] = 3    # actually not implemented
      sage: p
      [1,3,2]

Breaks (1), (5). This also means that any method that works on a list will not work on a permutation. So one would have to define a separate methods for a permutation.

- Use functional notation

      sage: p = DiscreteFunction([3,1,2])
      sage: p(1)
      3
      sage: p(1) = 1; p(2) = 3    # actually not implemented
      sage: p
      [1,3,2]

Caveat: requires patching Sage (no {{{__setcall__}}} analoguous to {{{__setitem__}}). In the mean time, we could use p.set(1, 1) (lengthy notation). Another (huge) disadvantage is that {{{__call___}}} is much slower than {{{__getitem__}}}

    sage: p = Permutations(130).random_element()
    sage: %timeit p[83]
    1000000 loops, best of 3: 808 ns per loop
    sage: %timeit p.__getitem__(83)
    1000000 loops, best of 3: 561 ns per loop
    sage: %timeit p(83)
    100000 loops, best of 3: 3.27 µs per loop

Actually something that I have always wonder about: why don't we have Permutation_class inheriting from list/tuple? This would speed things up.

    sage: from sage.combinat.permutation import Permutation_class
    sage: class MyPermutation(list, Permutation_class):
    ...      def __repr__(self):
    ...          return '[%s]' % super(MyPermutation,self).__repr__()[1:-1]
    sage: q = MyPermutation(Permutations(17).random_element()); q
    [2, 8, 12, 7, 9, 3, 11, 15, 14, 4, 5, 1, 6, 17, 16, 13, 10]
    sage: %timeit q[11]
    10000000 loops, best of 3: 89 ns per loop
    sage: %timeit q.__getitem__(11)
    1000000 loops, best of 3: 304 ns per loop
    sage: %timeit q(11)
    1000000 loops, best of 3: 1.2 µs per loop

- ...