[sympy] 3518 - fix Bell and necklace generation (#1666)

5 views
Skip to first unread message

Christopher Smith

unread,
Nov 21, 2012, 4:57:29 PM11/21/12
to sympy/sympy

http://code.google.com/p/sympy/issues/detail?id=3518

You can merge this Pull Request by running:

  git pull https://github.com/smichr/sympy 3518

Or view, comment on, or merge it at:

  https://github.com/sympy/sympy/pull/1666

Commit Summary

  • 3518: fix necklace routine
  • fix Bell permutation generation

File Changes

  • M sympy/utilities/iterables.py (221)
  • M sympy/utilities/tests/test_iterables.py (40)

Patch Links

—
Reply to this email directly or view it on GitHub.

Julien Rioux

unread,
Nov 21, 2012, 10:51:10 PM11/21/12
to sympy/sympy

SymPy Bot Summary: :eight_spoked_asterisk: Passed after merging smichr/3518 (009dee2) into master (f0984bd).
:eight_spoked_asterisk:PyPy 1.9.1-dev-0; 2.7.3-final-42: pass
:eight_spoked_asterisk:Python 2.7.2-final-0: pass
:eight_spoked_asterisk:Python 3.2.1-final-0: pass
:eight_spoked_asterisk:Sphinx 1.1.3: pass

Aaron Meurer

unread,
Nov 21, 2012, 11:36:16 PM11/21/12
to sympy/sympy

SymPy Bot Summary: :red_circle: Failed after merging smichr/3518 (009dee2) into master (f0984bd).
@smichr: Please fix the test failures.
:eight_spoked_asterisk:Python 2.5.0-final-0: pass
:eight_spoked_asterisk:Python 2.6.6-final-0: pass


:eight_spoked_asterisk:Python 2.7.2-final-0: pass

:eight_spoked_asterisk:Python 2.6.8-final-0: pass
:eight_spoked_asterisk:Python 2.7.3-final-0: pass


:eight_spoked_asterisk:PyPy 1.9.1-dev-0; 2.7.3-final-42: pass

:eight_spoked_asterisk:Python 3.2.2-final-0: pass
:eight_spoked_asterisk:Python 3.3.0-final-0: pass
:eight_spoked_asterisk:Python 3.2.3-final-0: pass
:eight_spoked_asterisk:Python 3.3.0-final-0: pass
:eight_spoked_asterisk:Python 3.3.0-final-0: pass
:red_circle:**Sphinx 1.1.3:** fail

Christopher Smith

unread,
Nov 22, 2012, 2:31:55 AM11/22/12
to sympy/sympy

This is ready to go, I believe. I don't think the Sphinx errors are mine.

Christopher Smith

unread,
Nov 22, 2012, 2:57:17 AM11/22/12
to sympy/sympy

These routines don't generate a lot of interest so I will commit tomorrow if there is no comment.

Christopher Smith

unread,
Nov 22, 2012, 3:21:40 AM11/22/12
to sympy/sympy

Other than lots of messages during building of the tutorials, I don't see any doc error problems (see below).


/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:2: WARNING: Literal block expected; none found.
looking for now-outdated files... none found
pickling environment... done
checking consistency... done
preparing documents... done
writing output... [100%] tutorial/tutorial                                      
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:1: WARNING: undefined label: guide (if the link has no caption the label must precede a section header)
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:1: WARNING: undefined label: module-docs (if the link has no caption the label must precede a section header)
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:1: WARNING: undefined label: guide (if the link has no caption the label must precede a section header)
/home/git/sympy/doc/src/tutorial/tutorial.en.rst:1: WARNING: undefined label: module-docs (if the link has no caption the label must precede a section header)
writing additional files... (0 module code pages) genindex search

Aaron Meurer

unread,
Nov 22, 2012, 4:57:57 AM11/22/12
to sympy/sympy

Those errors are from #1660. You can ignore them (unless you know how to fix them :)

Julien Rioux

unread,
Nov 22, 2012, 5:24:23 AM11/22/12
to sympy/sympy

SymPy Bot Summary: :eight_spoked_asterisk: Passed after merging smichr/3518 (8d62b16) into master (f3e3cc5).


:eight_spoked_asterisk:PyPy 1.9.1-dev-0; 2.7.3-final-42: pass

:eight_spoked_asterisk:Python 2.7.2-final-0: pass

:eight_spoked_asterisk:Python 3.2.1-final-0: pass
:eight_spoked_asterisk:Sphinx 1.1.3: pass

—


Reply to this email directly or view it on GitHub.

pernici

unread,
Nov 22, 2012, 9:59:17 AM11/22/12
to sympy/sympy

It seems strange to me that one cannot use list in this example

>>> from sympy.utilities.iterables import unrestricted_necklace
>>> list(unrestricted_necklace(3, 2))
[[0, 1, 1], [0, 1, 1]]

Julien Rioux

unread,
Nov 22, 2012, 8:13:56 PM11/22/12
to sympy/sympy

SymPy Bot Summary: :eight_spoked_asterisk: Passed after merging smichr/3518 (c00225b) into master (14c08c4).


:eight_spoked_asterisk:PyPy 1.9.1-dev-0; 2.7.3-final-42: pass
:eight_spoked_asterisk:Python 2.7.2-final-0: pass
:eight_spoked_asterisk:Python 3.2.1-final-0: pass
:eight_spoked_asterisk:Sphinx 1.1.3: pass

—


Reply to this email directly or view it on GitHub.

Christopher Smith

unread,
Nov 22, 2012, 11:53:46 PM11/22/12
to sympy/sympy

@pernici , I saw your comment (which was apparently deleted) and made a change to bell permutations so tuples are returned rather than the mutable list used to keep track of the permutations.

Christopher Smith

unread,
Nov 22, 2012, 11:54:07 PM11/22/12
to sympy/sympy

Merged #1666.

Rathmann

unread,
Dec 4, 2012, 2:09:10 PM12/4/12
to sympy/sympy

I know that this has been checked in for some time, but I thought I
would give it a belated look.

There was not a lot of fanfare surrounding this pull request, but it
looks like it is actually quite an important check-in. You are fixing
lots of things which were incorrect, or badly inefficient.

graycode.py -formatting only.

generate_bell(n)

  • Wow, the old implementation was using O(n!) memory? That is pretty
    sloppy, when there are well known memory-less algorithms.

    (Pulled up and ran old version - it was buggy, as I am sure you no
    doubt noticed -- list(generate_bell_old(3)) gives only 5 permutations,
    and more than one inversion separates adjacent perms.)

  • Is there a canonical definition of this permutation sequence?
    The wikipedia reference gives
    1 2 3
    1 3 2
    3 1 2
    3 2 1
    2 3 1
    2 1 3

    As the expected sequence. Knuth gives the same (but for n=4),
    1234, 1243, 1423, 4213, 4132...

    I can transform your sequence into the Wikipedia/Knuth sequences with
    for p in generate_bell(3):
    print [3-i for i in reversed(p)]

    or

    for p in generate_bell(4):
    print [4-i for i in reversed(p)]

    (Note, that Wikipedia and Knuth are 1-based in their element
    naming. That seems like a matter of taste.)

    I am not particularly suggesting that the checked-in version be
    changed, especially since I don't know what are the use cases for
    bell permutations. (And it is not called elsewhere in Sympy.)
    This implementation certainly meets the spec of only one inversion
    between adjacent permutations.

    I don't imagine anyone was depending on the old behavior, since it
    was so broken, and no bugs were filed.

generate_involutions().

Old version of this function was buggy in that it returned some
non-involutions.

New version gives correct number (140152) of involutions up to
n=12 9the highest I checked) but takes a long time to do so -- 150
seconds, or about .001
seconds/involution. After looking at the code, this makes sense.
This code does a generate-and-filter on all permutations, so of
course it is going to be slow for large n. This does make for a
simple and robust implementation.

Eventual enhancement request would be to put in a more efficient
algorithm. For example, Knuth gives an algorithm as the answer to
exercise 101, section 7.2.1.2. Answer on page 719. (I haven't
tried to understand that algorithm; I just looked it up..) The are
probably other implementations around on the web.

generate_derangements()
Similar approach as with involutions. Even has a TODO in the
docstring to replace with ECO approach.

All in all, no argument that this was good to check in.

Christopher Smith

unread,
Dec 24, 2012, 2:29:22 AM12/24/12
to sympy/sympy

@pkrathmann2 , thanks very much for looking this over. I don't plan any changes at this time. I'll defer to anyone else regarding, for example, the order that bell permutations should come back.

Rathmann

unread,
Dec 27, 2012, 6:03:27 PM12/27/12
to sympy/sympy

Hi Christopher,

If you get a chance to look at issue 3563, I would much appreciate your guidance.

No rush, I won't get a chance to get back to coding before the New Year.

Thanks

Reply all
Reply to author
Forward
0 new messages