Diff for "combinat/01" - Sagemath Wiki

Differences between revisions 1 and 2

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.

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)

- 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)

-  ⇤ ← Revision 1 as of 2009-07-27 13:31:33 → 
  Size: 1323
  Editor: NicolasThiery
  Comment:
+   ← Revision 2 as of 2009-07-27 13:56:03 → ⇥
  Size: 2416
  Editor: NicolasThiery
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 8:
- - Python mantra: an object which looks like a list should behave like a list.
+(1) Python mantra: an object which looks like a list should behave like a list.
 Line 21:
- - The user should be able to manipulate permutations (functions) of
   any finite set, and manipulate them as is, without translations::
+(2) The user should be able to manipulate permutations (functions) of
    any finite set, and manipulate them as is, without reindexing::
 Line 35:
-   In particular, whatever the syntax is, one want to be able to do::
    {{{
+    In particular, whatever the syntax is, one want to be able to do::
     {{{
 Line 42:
-    }}}
+     }}}
 Line 44:
+    It is important to have short notations for readability of the
    algorithms. Write access (with surrounding mutability mantra)
    is necessary as well.
-Line 45:
+Line 48:
- - Permutations(n) should be Permutations([1,...,n])
+(3) Permutations(n) should be Permutations([1,...,n])
-Line 47:
+Line 50:
- - Internally, permutations should be implemented as permutations of
+(4) Internally, permutations could be implemented as permutations of
-Line 49:
+Line 52:
+    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.
-Line 52:
+Line 60:
- - current one::
+ - Current one::
-Line 54:
+Line 62:
-      sage: p = Permutation([3,1,2])
+      sage: p = DiscreteFunction([3,1,2])
-Line 58:
+Line 66:
+      sage: p
      [1,3,2]
-Line 59:
+Line 69:
+   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)

 - 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)

 -