Diff for "combinat/01"

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

- ...