#5288: [with patch, not ready for review] cython gray code iterator for
k-combinations of a set
-----------------------------+----------------------------------------------
Reporter: dgordon | Owner: mhansen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.8
Component: combinatorics | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by ppurka):
* upstream: => N/A
Comment:
I think this patch should get merged, whether or not the generic iterator
gets written. It's already been three years since this patch was
submitted. `combinations()` in Sage-4.7.2 is pretty broken and gives
arcane errors. For example like this:
{{{
sage: combinations([vector([1,1]), vector([2,2]), vector([3,3])], 2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "_sage_input_81.py", line 10, in <module>
exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8
-*-\\n" +
_support_.preparse_worksheet_cell(base64.b64decode("Y29tYmluYXRpb25zKFt2ZWN0b3IoWzEsMV0pLCB2ZWN0b3IoWzIsMl0pLCB2ZWN0b3IoWzMsM10pXSwgMik="),globals())+"\\n");
execfile(os.path.abspath("___code___.py"))
File "", line 1, in <module>
File "/tmp/tmpNUZznv/___code___.py", line 3, in <module>
exec compile(u'combinations([vector([_sage_const_1 ,_sage_const_1 ]),
vector([_sage_const_2 ,_sage_const_2 ]), vector([_sage_const_3
,_sage_const_3 ])], _sage_const_2 )
File "", line 1, in <module>
File "/home/punarbasu/Installations/sage-4.7.2/local/lib/python2.6/site-
packages/sage/combinat/combinat.py", line 2016, in combinations
ans=gap.eval("Combinations(%s,%s)"%(mset,ZZ(k))).replace("\n","")
File "/home/punarbasu/Installations/sage-4.7.2/local/lib/python2.6/site-
packages/sage/interfaces/gap.py", line 374, in eval
result = Expect.eval(self, input_line, **kwds)
File "/home/punarbasu/Installations/sage-4.7.2/local/lib/python2.6/site-
packages/sage/interfaces/expect.py", line 1039, in eval
for L in code.split('\n') if L != ''])
File "/home/punarbasu/Installations/sage-4.7.2/local/lib/python2.6/site-
packages/sage/interfaces/gap.py", line 518, in _eval_line
raise RuntimeError, message
RuntimeError: Gap produced error output
Permutation: cycles must be disjoint and duplicate-free
executing Combinations([(1, 1), (2, 2), (3, 3)],2);
}}}
And like this:
{{{
sage: F.<a> = GF(4, 'a'); V = list(VectorSpace(F, 2)); combinations(V, 1)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "_sage_input_78.py", line 10, in <module>
exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8
-*-\\n" +
_support_.preparse_worksheet_cell(base64.b64decode("Ri48YT4gPSBHRig0LCAnYScpOyBWID0gbGlzdChWZWN0b3JTcGFjZShGLCAyKSk7IGNvbWJpbmF0aW9ucyhWLCAxKQ=="),globals())+"\\n");
execfile(os.path.abspath("___code___.py"))
File "", line 1, in <module>
File "/tmp/tmpXtx6m9/___code___.py", line 3, in <module>
exec compile(u"F = GF(_sage_const_4 , 'a', names=('a',)); (a,) =
F._first_ngens(1); V = list(VectorSpace(F, _sage_const_2 ));
combinations(V, _sage_const_1 )" + '\n', '', 'single')
File "", line 1, in <module>
File "/home/punarbasu/Installations/sage-4.7.2/local/lib/python2.6/site-
packages/sage/combinat/combinat.py", line 2017, in combinations
return eval(ans)
File "<string>", line 0
^
SyntaxError: unexpected EOF while parsing
}}}
Something as simple as this works with both examples because it doesn't
care what the items inside the list are:
{{{
def binom(S, k):
# S is a list, k is a number
def _binom(S, k):
if len(S) < k:
return
elif len(S) == k:
yield S
elif k == 1:
for s in S:
yield [s]
else:
for i,s in enumerate(S):
for ss in binom(S[(i+1):], k-1):
yield [s]+ss
return list(_binom(S, k))
}}}
I suppose the above implementation in cython will be already faster than
this python code, and it also seems to use a very specific algorithm which
is meant to be fast.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5288#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
