Permutation(list) should check its input (?)

[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:

[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.

[nharris]

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
----------------------------------------------------------------------

[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.

[brunellus]

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

[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?

[mhansen]

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