replace gap.eval with libgap calls in combinat/combinat.py

[rws]

As first reported in #15625 (comment:7) with lucas_number1, the same problem is encountered with gap evaluation of Stirling numbers:

sage: stirling_number1(1000,2)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-22-b29f3b3e2003> in <module>()
----> 1 stirling_number1(Integer(1000),Integer(2))

/home/ralf/sage/local/lib/python2.7/site-packages/sage/combinat/combinat.pyc in stirling_number1(n, k)
    650     """
    651     return Integer(gap.eval("Stirling1({0},{1})".format(Integer(n),
--> 652                                                         Integer(k))))
    653 
    654 

/home/ralf/sage/local/lib/python2.7/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (build/cythonized/sage/rings/integer.c:7902)()

TypeError: unable to convert x (=<integer 301...000 (2566 digits)>) to an integer

The way to go would be to replace gap.eval with libgap.eval and it's faster, too:

sage: timeit('Integer(gap.eval("Stirling1(100,2)"))')
625 loops, best of 3: 419 µs per loop
sage: timeit('libgap.eval("Stirling1(100,2)").sage()')
625 loops, best of 3: 125 µs per loop
sage: timeit('libgap.eval("Stirling1(1000,2)").sage()')
125 loops, best of 3: 6.45 ms per loop

Addendum: even faster would be to use (n-1)!*H(n-1) for stirling(n,2), dependent on #16671:

sage: harmonic_number(99)*factorial(99)==stirling_number1(100,2)
True
sage: timeit('harmonic_number(99)*factorial(99)')
625 loops, best of 3: 56.9 µs per loop
sage: timeit('harmonic_number(999)*factorial(999)')
625 loops, best of 3: 119 µs per loop

[tscrim]

Also with #16380 (which I've added as a dependency because it's not been put into a release yet), we don't have to worry about the startup time of libgap anymore (which was really annoying). +1 to doing this.

[rws]

This is blocked by:

sage: ans=libgap.eval("UnorderedTuples(['a','b','c'],2)")
sage: type(ans)
<type 'sage.libs.gap.element.GapElement_List'>
sage: a=ans.sage()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-4-43379484318b> in <module>()
----> 1 a=ans.sage()

/home/ralf/sage/local/lib/python2.7/site-packages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement_List.sage (build/cythonized/sage/libs/gap/element.c:14661)()

/home/ralf/sage/local/lib/python2.7/site-packages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement_List.sage (build/cythonized/sage/libs/gap/element.c:14661)()

/home/ralf/sage/local/lib/python2.7/site-packages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement.sage (build/cythonized/sage/libs/gap/element.c:8749)()

See #16750

[vbraun]

New commits:

​16922b5

16719: replace gap with libgap

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​843ba48	Convert Gap chars into Python strings
​b69d63f	Merge branch 'u/vbraun/libgap_fails_converting_string_gapelements_to_sage' of trac.sagemath.org:sage into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

[rws]

OK, now that strings get to GAP, back they get as GapElement_List of chars:

sage: ans = libgap.eval("UnorderedTuples(['a', 'b', 'c'],2)"); ans
[ "aa", "ab", "ac", "bb", "bc", "cc" ]
sage: type(ans[0])
<type 'sage.libs.gap.element.GapElement_List'>
sage: ans.sage()
[["'a'", "'a'"],
 ["'a'", "'b'"],
 ["'a'", "'c'"],
 ["'b'", "'b'"],
 ["'b'", "'c'"],
 ["'c'", "'c'"]]

Shouldn't lists of chars be converted to strings?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​240cc10

16719 reviewer's patch: attempt to fix previous patch

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​47f0796	Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
​7cc26d5	Improve GAP String handling
​6fe1fc5	Treat the empty GAP list as list and not as string
​6a4892d	Merge branch 't/16750/libgap_fails_converting_string_gapelements_to_sage' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
​a1269fb	16719: unordered_tuples() distinguishes now between set types

[rws]

It felt more natural to give tuples of chars as string, but tuples of char+string as list of strings. If the latter had been the original behaviour the GAP T_CHAR hassle wouldn't have been necessary.

Please review.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e82786b

Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

[tscrim]

Note that this will conflict with #13982 for unordered_tuples (FYI I handled GAP's output as strings differently).

[rws]

I wouldn't mind removing the unordered tuples bit from this patch, especially for speed reasons, and choice of algorithm. It's just that I don't like it that you simply remove that doctest that results in ['aa', 'ab', 'ac', 'bb', 'bc', 'cc']. I think you should support it.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5b156ad

16719: revert change to unordered_tuples(), handled by 13982

[jdemeyer]

For bell_number(), I'm making the change at #17157, so you can remove that piece.

[jdemeyer]

Reviewer patch needs review.

---

New commits:

​0266cef	Improve formula for Bell numbers
​fd22966	Merge branch 'ticket/17157' into ticket/16719
​4339c50	Remove superfluous type conversions, use libgap for unordered_tuples()

[vbraun]

The reviewer commits look good to me. I've added a patch to make the calls to my beautiful library interface less ugly ;-)

---

New commits:

​9f4777d

Beautify libgap calls

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

​34c9b4c	Changes from the reviewers.
​b47af6a	A minor tweaking of the doc.
​53a9d7e	Families return output based on order of variable names. Fixed coercion issue.
​339b71d	Fixed some typos.
​3ce3f6a	Merge branch 'public/algebras/weyl_clifford-15300' of git://trac.sagemath.org/sage into clifford
​8698275	lifting bilinear forms onto exterior algebras
​a002f4b	Some tweaks to lifted_bilinear_form and fixed doctest.
​ff27bdc	further fixes
​330617c	Merge commit 'ff27bdc5d87967d0e7fd5c1305cef4340db816c7' into ticket/17157
​d6698e2	Merge already-closed #17157 to resolve conflict