Cleanup in choose_nk, split_nk, subword, subset

[videlec]

• deprecate ChooseNK (in sage.combinat.choose_nk) and SplitNK (in sage.combinat.split_nk).
• clean sage.combinat.subword and sage.combinat.subset
  • inheritance from Parent
  • much better iteration/random generation
  • ...

And become more pep8 compliant ;=)

see also: #16472

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: generation, set, subset, partition

Author: Vincent Delecroix, Frédéric Chapoton

Branch/Commit: 714f266

Reviewer: Florent Hivert, Frédéric Chapoton, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/10534

[videlec]

Description changed:

--- 
+++ 
@@ -1,31 +1,36 @@
-This ticket stands for a faster implementation of subset and partition generation of (finite or infinite) enumerated sets.
+This ticket stands for a faster method of exhaustive generation of
 
-The timing for anything related to Sage sage.combinat.Subwords, sage.combinat.Subsets, sage.combinat.SetPartitions, ... are very slow. The roadmap is as follows
+* subwords
+* subsets
+* set partitions
 
-1) **Low level generation:** Implement a small python extension which must be as performant as itertools is
+Moreover we correct bugs and typos (see details in the patch) and create some random generation capabilities.
+
+Timings (on Intel(R) Core(TM)2 Duo CPU T8100  @ 2.10GHz)
+
+Old version
 
 ```
-sage: import itertools
-sage: list(itertools.combinations(['a','b','c'],2))
-[('a', 'b'), ('a', 'c'), ('b', 'c')]
+sage: S = SetPartitions(8,[3,3,2])
+sage: timeit('for p in S: pass')
+5 loops, best of 3: 401 ms per loop
+
+sage: S = SetPartitions(9,[3,3,2,1])
+sage: timeit('for p in S: pass')
+5 loops, best of 3: 4 s per loop
 ```
+New version
 
-The following will be available:
+```
+sage: S = SetPartitions(8,[3,3,2])
+sage: timeit('for p in S: pass')
+5 loops, best of 3: 130 ms per loop
+sage: timeit('for p in S._fast_iterator(): pass')
+25 loops, best of 3: 10.4 ms per loop
 
-* subset of given size
-* all subsets
-* set partitions with given integer combination
-* all set partitions
-
-And for each of them different order of generation (lex, revlex, Gray codes, ...) and output as list or tuple.
-
-Any Suggested names for iterators?
-
-combinations_lex_as_list, combinations_lex_as_tuple combinations_revlex_as_
-
-2) **Include and interface it with Sage:** this won't be hard.
-
-REFERENCES:
-
-* Knuth TAOCP fascicule 3a
-* Python C API http://docs.python.org/c-api/
+sage: S = SetPartitions(9,[3,3,2,1])
+sage: timeit('for p in S: pass')
+5 loops, best of 3: 1.47 s per loop
+sage: timeit('for p in S._fast_iterator(): pass')
+5 loops, best of 3: 94.1 ms per loop
+```

[videlec]

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@
 * subsets
 * set partitions
 
-Moreover we correct bugs and typos (see details in the patch) and create some random generation capabilities.
+Moreover we correct bugs and typos (see details in the patch, doctest coverage is now 100%) and create some random generation capabilities.
 
 Timings (on Intel(R) Core(TM)2 Duo CPU T8100  @ 2.10GHz)
 
@@ -30,7 +30,7 @@
 
 sage: S = SetPartitions(9,[3,3,2,1])
 sage: timeit('for p in S: pass')
-5 loops, best of 3: 1.47 s per loop
+5 loops, best of 3: 1.43 s per loop
 sage: timeit('for p in S._fast_iterator(): pass')
-5 loops, best of 3: 94.1 ms per loop
+5 loops, best of 3: 91.3 ms per loop
 ```

[videlec]

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@
 
 * subwords
 * subsets
-* set partitions
+* set partitions (ordered and non orderered)
 
 Moreover we correct bugs and typos (see details in the patch, doctest coverage is now 100%) and create some random generation capabilities.
 

[videlec]

Description changed:

--- 
+++ 
@@ -5,6 +5,8 @@
 * set partitions (ordered and non orderered)
 
 Moreover we correct bugs and typos (see details in the patch, doctest coverage is now 100%) and create some random generation capabilities.
+
+To fit with FiniteEnumeratedSet, cardinality returns now a Sage Integer (and no more a Python int).
 
 Timings (on Intel(R) Core(TM)2 Duo CPU T8100  @ 2.10GHz)
 
@@ -34,3 +36,5 @@
 sage: timeit('for p in S._fast_iterator(): pass')
 5 loops, best of 3: 91.3 ms per loop
 ```
+
+