16719: replace gap with libgap
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

* 'u/vbraun/libgap_fails_converting_string_gapelements_to_sage' of trac.sagemath.org:sage:
  Convert Gap chars into Python strings
16719 reviewer's patch: attempt to fix previous patch
Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

* develop: (52 commits)
  Updated Sage version to 6.3.rc0
  Reverted change of using format instead of %.
  Last minor tweak.
  Some tweaks fixing things from #2516.
  trac #16709: Broken doc
  Do not add /usr/local/{lib,include} to paths
  remove stray without-flint
  trac #15181: Reviewer's remarks
  fixed typos in dostrings
  Stupid typo...
  Some more review tweaks and fixes.
  trac #16738 removing tests again
  trac #16738 better choice of what to test in reasonable amount of time
  trac #15191 change bad syntax of 2 input blocks
  added a non-generic examples, and some minor changes
  trac #16741: Bug in IncidenceStructure.relabel when the ground set consists of pairs
  trac 16XXX shortening some cluster doctests
  trac #16732: make _maxima_init_evaled_ implementations and some bracket translations more robust The changes here make sure that a few _maxima_init_evaled_ routines process their arguments with _maxima_init_ rather than just make strings out of them, as well as fix the maxima_string_to_expression parser to properly handle possible nested square brackets.
  Micro-optimizations to the *_generators.
  Fixed trivial failing doctests.
  ...
Merge branch 't/16750/libgap_fails_converting_string_gapelements_to_sage' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

* t/16750/libgap_fails_converting_string_gapelements_to_sage:
  Treat the empty GAP list as list and not as string
  Improve GAP String handling

Conflicts:
	src/sage/libs/gap/element.pyx
16719: unordered_tuples() distinguishes now between set types
Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

* develop: (480 commits)
  Updated Sage version to 6.4.beta1
  Reviewer's Commit: Fixed the failing doctest.
  Send include_dirs to Cython for dependency checking
  Fix alarm doctest (but not the underlying problem)
  Fix yet another division by zero in Fp(t)
  Fixed trivial doctest failure due to new format.
  vi-induced typo in #16847
  more typos in rst docs
  typo from #16714(comment 59)
  Added crossref from G.order() to G.degree() in permgroup
  Fixed typo
  Fixed failing doctest in permutation.py
  Fixed is_bistochastic to make sure all entries in the matrix are nonnegative
  trac #15140: Broken doctests
  Fix and test for Kashiwara convention of tensor products.
  Made changes that Nicolas and I talked about.
  Better IMO short_repr method and made some lines shorter/logically line broken.
  Added multiplicative abelian groups to the catalog.
  trac #16665: cosmetic
  trac #16665: New OA for n=408,600,792,856,1368,2328,...
  ...
16719: revert change to unordered_tuples(), handled by 13982
Merge branch 'ticket/17157' into ticket/16719
Remove superfluous type conversions, use libgap for unordered_tuples()
Relax assumptions for bitset functions
Move bitset to sage.data_structures
Import data_structures into global namespace
Fix for pickling NC rings with weighted term order.
Beautify libgap calls
Merge already-closed #17157 to resolve conflict

Conflicts:
	src/sage/combinat/combinat.py
Trac #16719: replace gap.eval with libgap calls in combinat/combinat.py

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

URL: http://trac.sagemath.org/16719
Reported by: rws
Ticket author(s): Ralf Stephan
Reviewer(s): Jeroen Demeyer, Volker Braun
Trac #17196: Relax assumptions on bitset operations

Most bitset operations state something like
{{{
    We assume the two sets have the same size.  Otherwise, the
    behavior of this function is undefined and the function may
    segfault.
}}}

However, in fact most of these requirements can be relaxed.

In many cases, I simply change the comment to indicate what the real
conditions are. For shifts, I actually change the implementation
slightly such that the condition becomes `r.size <= a.size + n` which is
useful for #15820.

Also move bitsets to `src/sage/data_structures`.

URL: http://trac.sagemath.org/17196
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer, Simon King
Reviewer(s): Simon King
Trac #17224: Fix pickling of NC rings with weighted term order

The term order is pickled by the name rather than the object
`TermOrder`. This causes problems for term orders which need additional
arguments.
{{{
sage: from sage.rings.polynomial.term_order import TermOrder
sage: F.<x,y> = FreeAlgebra(QQ)
sage: g = F.g_algebra({y*x:-x*y}, order=TermOrder('wdegrevlex', [1,2]))
sage: loads(dumps(g)) # Boom
}}}

URL: http://trac.sagemath.org/17224
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): Miguel Marco