#15595: Shuffle Product
-------------------------------------+-------------------------------------
Reporter: elixyre | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jean-Baptiste | Reviewers:
Priez | Work issues:
Report Upstream: N/A | Commit:
Branch: | 66c0f3f2afe75a4867885c874c26f72220b4c63a
u/elixyre/ticket/15595 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Description changed by elixyre:
Old description:
> Shuffle product can be define on any iterable object so I propose to
> define a new class that implement an efficient shuffle product on
> iterables.
>
> Currently one has two shuffle product in Sage, one is defined on words
> and one is defined on permutations.
>
> The first one is slow and don't allow to compute shuffle of two list and
> the second is fast but only defined for Permutations.
>
> Some benchmarks:
>
> My Shuffle:
>
> Time if *ShuffleProduct* inherits just of *SageObject*
>
> {{{
> sage: from sage.combinat.shuffle import ShuffleProduct
> sage: a = Word("abcdefghij")
> sage: b = Word("klmnopqrst")
> sage: %time _ = list(ShuffleProduct(a, b, Word))
> CPU times: user 17 s, sys: 994 ms, total: 18 s
> Wall time: 18.4 s
> }}}
>
> Time if *ShuffleProduct* inherits of the evil class *Parent*:
>
> {{{
> sage: from sage.combinat.shuffle import ShuffleProduct
> sage: a = Word("abcdefghij")
> sage: b = Word("klmnopqrst")
> sage: %time _ = list(ShuffleProduct(a, b, Word))
> CPU times: user 32.5 s, sys: 1.7 s, total: 34.2 s
> Wall time: 34.5 s
> }}}
>
> Comparaison with *ShuffleProduct_w1w2*:
>
> {{{
> sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2
> as Shuffle
> sage: %time _ = list(Shuffle(a, b))
> CPU times: user 59.66 s, sys: 0.29 s, total: 59.94 s
> Wall time: 59.90 s
> }}}
New description:
Shuffle product can be define on any iterable object so I propose to
define a new class that implement an efficient shuffle product on
iterables.
Currently one has two shuffle product in Sage, one is defined on words and
one is defined on permutations.
The first one is slow and don't allow to compute shuffle of two list and
the second is fast but only defined for Permutations.
Some benchmarks:
My Shuffle:
Time if *ShuffleProduct* inherits just of *SageObject*
{{{
sage: from sage.combinat.shuffle import ShuffleProduct
sage: a = Word("abcdefghij")
sage: b = Word("klmnopqrst")
sage: %time _ = list(ShuffleProduct(a, b, Word))
CPU times: user 17 s, sys: 994 ms, total: 18 s
Wall time: 18.4 s
}}}
Time if *ShuffleProduct* inherits of the evil class *Parent*:
{{{
sage: from sage.combinat.shuffle import ShuffleProduct
sage: a = Word("abcdefghij")
sage: b = Word("klmnopqrst")
sage: %time _ = list(ShuffleProduct(a, b, Word))
CPU times: user 32.5 s, sys: 1.7 s, total: 34.2 s
Wall time: 34.5 s
}}}
with
{{{
Parent.__init__(self, category=FiniteEnumeratedSets())
}}}
Comparaison with *ShuffleProduct_w1w2*:
{{{
sage: from sage.combinat.words.shuffle_product import ShuffleProduct_w1w2
as Shuffle
sage: %time _ = list(Shuffle(a, b))
CPU times: user 59.66 s, sys: 0.29 s, total: 59.94 s
Wall time: 59.90 s
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15595#comment:8>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
