Opened 5 years ago

Closed 5 years ago

#24434 closed enhancement (fixed)

faster reduced words

Reported by: Martin Rubey Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords:
Cc: Darij Grinberg, Travis Scrimshaw Merged in:
Authors: Martin Rubey Reviewers: Darij Grinberg, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: bed22ef (Commits, GitHub, GitLab) Commit: bed22efa99dfbfdf508449f41d81b6633afaa7e3
Dependencies: Stopgaps:

Status badges

Description (last modified by Martin Rubey)

Since it is usually infeasible to compute all reduced words of a permutation, an iterator may be more convenient.

As a side effect, the performance is also a bit better. Old:

sage: %timeit [len(pi.reduced_words()) for pi in Permutations(6)]
1 loop, best of 3: 42.3 s per loop
sage: version()
'SageMath version 8.2.beta1, Release Date: 2017-12-22'

New:

sage: %timeit [len(pi.reduced_words()) for pi in Permutations(6)]
1 loop, best of 3: 4.9 s per loop

Change History (9)

comment:1 Changed 5 years ago by Martin Rubey

Branch: u/mantepse/faster_reduced_words

comment:2 Changed 5 years ago by Martin Rubey

Authors: Martin Rubey
Cc: Darij Grinberg Travis Scrimshaw added
Commit: 14bfedbb03d4a82750731586d3a667376e2d8bad
Component: PLEASE CHANGEcombinatorics
Description: modified (diff)
Status: newneeds_review
Type: PLEASE CHANGEenhancement

comment:3 Changed 5 years ago by Darij Grinberg

Looks good to me (if the tests path)!

Version 1, edited 5 years ago by Darij Grinberg (previous) (next) (diff)

comment:4 Changed 5 years ago by git

Commit: 14bfedbb03d4a82750731586d3a667376e2d8bad234661711ef519723bc5fe252941c0fed2e9b577

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

2346617python3 fix and fix doc

comment:5 Changed 5 years ago by Martin Rubey

(the patchbots are failing on 8.2beta1, not on this ticket)

comment:6 Changed 5 years ago by Travis Scrimshaw

Reviewers: Darij Grinberg, Travis Scrimshaw

One little thing:

-return [w for w in self.reduced_words_iterator()]
+return list(self.reduced_words_iterator())

Once done, you can set a positive review on my behalf.

comment:7 Changed 5 years ago by git

Commit: 234661711ef519723bc5fe252941c0fed2e9b577bed22efa99dfbfdf508449f41d81b6633afaa7e3

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

bed22efuse list to turn iterator into list

comment:8 Changed 5 years ago by Martin Rubey

Status: needs_reviewpositive_review

Wonderful, thank you!

comment:9 Changed 5 years ago by Volker Braun

Branch: u/mantepse/faster_reduced_wordsbed22efa99dfbfdf508449f41d81b6633afaa7e3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.