Opened 11 years ago

Closed 8 years ago

#9831 closed defect (duplicate)

Permutation(list) should check its input (?)

Reported by: mmezzarobba Owned by: sage-combinat
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords:
Cc: brunellus Merged in:
Authors: Neal Harris Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mmezzarobba)

It seems that Permutation(list) requires that the elements of list are exactly 1, 2, ..., n, but this is not clearly documented. Other values of list are accepted without error and lead to strange behaviours later.

When list contains 0:

~$ ulimit -v 1048576 
~$ sage
----------------------------------------------------------------------
| Sage Version 4.5.1, Release Date: 2010-07-19                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: Permutation([1]).signature()
1
sage: Permutation([0]).signature()
-1
sage: Permutation([1,0]).signature()
-1
sage: Permutation([0,1]).signature()
---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)

/home/marc/<ipython console> in <module>()

/data/sage-4.5.1/local/lib/python2.6/site-packages/sage/combinat/permutation.pyc in signature(p)
    739             -1
    740         """
--> 741         return (-1)**(len(p)-len(p.to_cycles()))
    742     
    743 

/data/sage-4.5.1/local/lib/python2.6/site-packages/sage/combinat/permutation.pyc in to_cycles(self, singletons)
    556             l[i], next = False, l[i]
    557             while next != cycleFirst:
--> 558                 cycle.append( next )
    559                 l[next - 1], next  = False, l[next - 1]
    560             #Add the cycle to the list of cycles

MemoryError:

With repeated elements:

sage: Permutation([1,1]).signature()
---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)

/home/marc/<ipython console> in <module>()

/data/sage-4.5.1/local/lib/python2.6/site-packages/sage/combinat/permutation.pyc in signature(p)
    739             -1
    740         """
--> 741         return (-1)**(len(p)-len(p.to_cycles()))
    742     
    743 

/data/sage-4.5.1/local/lib/python2.6/site-packages/sage/combinat/permutation.pyc in to_cycles(self, singletons)
    556             l[i], next = False, l[i]
    557             while next != cycleFirst:
--> 558                 cycle.append( next )
    559                 l[next - 1], next  = False, l[next - 1]
    560             #Add the cycle to the list of cycles

MemoryError:

Attachments (2)

trac_9831_Permutation_list_check.patch (4.4 KB) - added by nharris 10 years ago.
trac_9831_Permutation_input_repair.patch (2.2 KB) - added by brunellus 9 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 11 years ago by mmezzarobba

  • Description modified (diff)
  • Summary changed from Strange behaviour of Permutation(list) when list contains 0 to Permutation(list) should check its input (?)

comment:2 Changed 11 years ago by lftabera

Yes, Permutation should check the input. Moreover, it should be better documented.

In cycle notation:

sage: Permutation([(1,2),(3,4),(1,3)])
[3, 1, 1, 3]

which is not a permutation.

Changed 10 years ago by nharris

comment:3 Changed 10 years ago by nharris

  • Authors set to Neal Harris
  • Status changed from new to needs_work

I've uploaded a patch which takes care of this issue. (It also allows Permutation to take a list of non-disjoint tuples.) There's still some work to be done, as the patch breaks several doctests:

----------------------------------------------------------------------

The following tests failed:

	sage -t -long devel/sage-test/doc/en/bordeaux_2008/generators_for_rings.rst # 4 doctests failed
	sage -t -long devel/sage-test/sage/combinat/integer_vector_weighted.py # 7 doctests failed
	sage -t -long devel/sage-test/sage/combinat/posets/hasse_diagram.py # 1 doctests failed
	sage -t -long devel/sage-test/sage/combinat/posets/poset_examples.py # 6 doctests failed
	sage -t -long devel/sage-test/sage/misc/sagedoc.py # 3 doctests failed
	sage -t -long devel/sage-test/sage/modular/modform/find_generators.py # 18 doctests failed
	sage -t -long devel/sage-test/sage/plot/plot3d/base.pyx # 4 doctests failed
	sage -t -long devel/sage-test/sage/modular/ssmod/ssmod.py # Time out
----------------------------------------------------------------------

comment:4 Changed 9 years ago by brunellus

Please note that this ticket duplicates #8392, which also contains some patch. Moreover, it links to a discussion on combinat-devel, where an additional computational load of the check is considered.

Would you mind if I resolve failing doctests? I am new to the Sage development, so I am not sure whether someone is working on this issue right now.

comment:5 Changed 9 years ago by brunellus

  • Cc brunellus added

comment:6 Changed 9 years ago by brunellus

Large portion of the errors was caused by integer_vector_weighted that used permutation multiplication instead of permutation acting on list.

Changed 9 years ago by brunellus

comment:7 Changed 9 years ago by brunellus

Now, I would like to send this to review, because I see no more error (maybe I overlooked some?). But the original patch refuses to apply -- I guess it's because codebase shifted somehow in last year. Is this a problem I should correct?

comment:8 Changed 8 years ago by mhansen

  • Milestone changed from sage-5.11 to sage-duplicate/invalid/wontfix
  • Resolution set to duplicate
  • Status changed from needs_work to closed

This is indeed a duplicate of #8392 which has been merged.

Note: See TracTickets for help on using tickets.