Opened 6 years ago
Closed 6 years ago
#15439 closed defect (fixed)
sage/combinat/matrices/latin.py: isotopism method uses product of permutations
Reported by: | darij | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | combinatorics | Keywords: | permutation, combinat, latin square |
Cc: | ncohen, sage-combinat, nthiery, fhivert | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Darij Grinberg |
Report Upstream: | N/A | Work issues: | |
Branch: | u/ncohen/15439 (Commits) | Commit: | 400bdc1a102cedffd2170e5d21deebd11ec5b9ed |
Dependencies: | Stopgaps: |
Description
From sage/combinat/matrices/latin.py
:
def isotopism(p): """ Returns a Permutation object that represents an isotopism (for rows, columns or symbols of a partial latin square). Since matrices in Sage are indexed from 0, this function translates +1 to agree with the Permutation class. We also handle PermutationGroupElements. [...] x = x * isotopism(p[i]) [...]
This uses the syntax a * b
for the product of two permutations. This syntax is bad because its semantics depends on the state of a global variable (mult
in Permutation.global_options()
), which decides which of the factors is to be applied first when multiplying two permutations. I don't know if it matters for this particular method, but such things have been causing subtle bugs in two other places, so this should be looked at (unfortunately I don't know much about Latin squares; Nathann?). Even if the result doesn't depend on the order of multiplication, it is better to use the _left_to_right_multiply_on_left
and _left_to_right_multiply_on_right
methods of class sage.combinat.permutation.Permutation
for speed reasons (they don't waste time looking up the state of that global variable).
See also #15174.
Change History (19)
comment:1 follow-up: ↓ 2 Changed 6 years ago by
- Cc nthiery fhivert added
comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 6 years ago by
Hi Nathann,
Replying to ncohen:
4) This code has *NOTHING* to do there. Its only purpose is to accept any kind of permutation input on 0..n-1 and to output a permutation on 1..n. It's like this code should appear in the constructor of
Permutations
, with a flagtranslate_from_0n_to_1n=True
Good point. I'm not sure if I want to add a translate_from_0n_to_1n
variable to the Permutation
constructor (that constructor is already quite complex, and it gets called a hell lot). But maybe we should add a function to sage/combinat/permutation.py
which constructs a permutation from its "left shift by 1"?
1) I did not know what an isotopism was either, and it looks like we could add a link toward the following Wikipedia page if we patch this file : http://en.wikipedia.org/wiki/Latin_square#Equivalence_classes_of_Latin_squares
+1 for the link. It just doesn't have much to do with the isotopism
method; it probably should be in the apply_isotopism
docstring.
2) "Morally", this '*' can be any of the two actions, as it should only apply to permutations with disjoint supports : this part of the function builds a permutation from a 'cycles notation', i.e.
'(1,2,3)(4,5)'
. It builds a permutation for each cycle and multiplies the results, so both actions should be fine.
OK, good point -- it seems that the isotopism
method is indeed meant to take disjoint cycles, whence the order is irrelevant. But I'm saying "seems" because to me, too, it's far from clear from the docstring. If we can confirm than this is what's meant, it should be rather easy to avoid the use of *
and probably even gain some speed this way.
3) Morally, this part of the code is made for disjoint cycles notations, but nothing actually checks that. And given a permutation in cycle notation (as a string)
'(1,2,3)(4,5)'
, don't you have the very same problem knowing in which order they should be applied ? Or is that clear for everybody ? I honestly ask the question, I personally always used permutations like function composition, and all that happens with this left/right action is beyond me:-P
For quite a long time I believed that everyone agreed pq
would mean "first do q
, then p
", apart from maybe some 19th century British authors (who would be unreadable anyway). But it turned out that the opposite convention is still around in Britain :(
5) Having something like
Permutations.global_options
which redefines the meaning of'*'
is *criminal*.
The global_options
constructor is just a new way to handle these global variables, but the global variable determining order of multiplication is not new. I guess it's nuclear waste from the olden days of Sage.
In #15174 it surfaced that with Permutations.global_options(mult) == 'l2r'
, the Hecke algebra (a deformation of the symmetric group algebra) would have its multiplication opposite of that of the symmetric group algebra, whereas with Permutations.global_options(mult) == 'r2l'
it would not be an algebra at all (associativity would not hold). I believe this has been around for ages. You've gotta love our codebase...
Greets,
Darij
comment:3 in reply to: ↑ 2 Changed 6 years ago by
Yoooooooooooo !!
Good point. I'm not sure if I want to add a
translate_from_0n_to_1n
variable to thePermutation
constructor (that constructor is already quite complex, and it gets called a hell lot). But maybe we should add a function tosage/combinat/permutation.py
which constructs a permutation from its "left shift by 1"?
Well... I'd say that having this exposed in the constructor would be cool, considering that I don't even get why the permutations are on 1..n in the first place. Accepting them on a 0..n-1 input, even to only return a 1..n one would be cool. But I tried to put some sense into what's happening in the combinat/ folder, and each time it crashes on a
1) We will do it some day
2) It's a good idea but it makes existing code slower (#14019 is in this case, though wrong results are actually returned in the meantime)
3) I have to ask XXXX, which never happens
So, well. Even though the only sensible thing would be to support at least both 0..n-1 and 1..n (why not LABELLED permutations btw ? Like PermutationGroupElement? already does ?). Even though the slightly less sensible thing would be to give this up but to be able to relabel them from the constructor, I think I can't hope for anything better than having a relabeling function that I could import and use manually.
+1 for the link. It just doesn't have much to do with the
isotopism
method; it probably should be in theapply_isotopism
docstring.
Right, right.
OK, good point -- it seems that the
isotopism
method is indeed meant to take disjoint cycles, whence the order is irrelevant. But I'm saying "seems" because to me, too, it's far from clear from the docstring. If we can confirm than this is what's meant, it should be rather easy to avoid the use of*
and probably even gain some speed this way.
Oh, I'm pretty sure that this is what is meant there. Of course nothing checks it (we are in the combinat/ folder after all) but it was done in the very same way in the constructor of permutations before #13742.
For quite a long time I believed that everyone agreed
pq
would mean "first doq
, thenp
", apart from maybe some 19th century British authors (who would be unreadable anyway). But it turned out that the opposite convention is still around in Britain :(
HMmmmmmmmm >_<
The
global_options
constructor is just a new way to handle these global variables, but the global variable determining order of multiplication is not new. I guess it's nuclear waste from the olden days of Sage.In #15174 it surfaced that with
Permutations.global_options(mult) == 'l2r'
, the Hecke algebra (a deformation of the symmetric group algebra) would have its multiplication opposite of that of the symmetric group algebra, whereas withPermutations.global_options(mult) == 'r2l'
it would not be an algebra at all (associativity would not hold). I believe this has been around for ages. You've gotta love our codebase...
Nightmares. Nightmares. Why don't we have "permutations acting on right" and "permutations acting on the left" then ? And get rid of a flag that might break dozens of functions without anybody knowing ?
Nathann
comment:4 Changed 6 years ago by
- Branch set to u/ncohen/15439
- Status changed from new to needs_review
Hello ! I tried twice to update the constructor of Permutation
to add a shift_input_by_one=False
flag, but each time it convinced me that it was bad work. Plus I don't think that this is the good way out -- the good way out is to have permutations on arbitrary objects.
Hence I did not touch permutation.py. Err, I just changed a few calls to all()
to prevent them from building a long useless list of [False, False, False, False]
. And I wrote the doc of this isotopism thing, and avoided this *
on multiplications.
But honestly, I think you have no way to ensure that nobody will ever use this *
in Sage code without worrying over this multiplication order.
Nathann
comment:5 Changed 6 years ago by
- Commit set to a1b05a808faf8052618f31f2eebd855082b7da29
comment:6 Changed 6 years ago by
- Branch changed from u/ncohen/15439 to u/darij/ticket/15439
- Created changed from 11/20/13 03:53:44 to 11/20/13 03:53:44
- Modified changed from 12/05/13 11:20:12 to 12/05/13 11:20:12
comment:7 Changed 6 years ago by
- Branch changed from u/darij/ticket/15439 to u/ncohen/15439
Review patch uploaded. I'd rather have put it into the public
namespace, but I've forgotten how to do that using the dev scripts (and if I use git manually, how do I reset the Branch field on the ticket?).
I put back one newline you removed since I found it reasonable.
meld seems to do creepy stuff; I have checked the sanity of the merge manually using diff.
comment:8 Changed 6 years ago by
- Branch changed from u/ncohen/15439 to u/darij/ticket/15439
- Modified changed from 12/10/13 08:02:20 to 12/10/13 08:02:20
comment:9 Changed 6 years ago by
- Commit changed from a1b05a808faf8052618f31f2eebd855082b7da29 to b484c8a59a690c0232097e4ae40ef58c6e813837
Hmmmmmm... The git history looks rather painful indeed :-P
Why this "pre-empting" patch ? And I didn't know anything about meld, though git merge does the job for me at the moment... :-P
Do you want to torture this branch further or can we set it to positive_review
? :-PPPPP
Nathann
New commits:
b484c8a | typo fixes |
752f72f | fixing merge errors |
b5eb9e4 | manual merge |
20ca024 | pre-empting Nathann's changes to permutation.py so as to make the merge less painful |
comment:10 Changed 6 years ago by
- Milestone changed from sage-5.13 to sage-6.0
- Status changed from needs_review to positive_review
Well, the edits to permutation.py
conflicted with my patch that was merged into beta5. So there was some merging involved. But apparently I cannot trust meld, since I tell it to merge all changes from the left version and it does not, in fact, merge all changes from the left version. (That or I did something wrong.)
I guess it's positive_review then?
comment:11 Changed 6 years ago by
HMmmmmm... Actually I would be quite glad to rewrite this branch and make it cleaner. Would it be fine if I just take my old branch, add your typo fixes into it, with all this atop beta5 ?
Nathann
comment:12 follow-up: ↓ 13 Changed 6 years ago by
I won't mind... I hope noone hangs on this branch now (is there a good way to find this out at least for branches on the trac server?).
comment:13 in reply to: ↑ 12 Changed 6 years ago by
- Branch changed from u/darij/ticket/15439 to u/ncohen/15439
- Commit changed from b484c8a59a690c0232097e4ae40ef58c6e813837 to 400bdc1a102cedffd2170e5d21deebd11ec5b9ed
Yooooooooo !
Here is a new updated branch. Is that good for you ?
I won't mind... I hope noone hangs on this branch now (is there a good way to find this out at least for branches on the trac server?).
Ahahahah. No, I don't think that there is. That's one of the big problems with git. Perhaps this will make people review patches quicker, who knows ? Perhaps they will be merged faster, too. I even wonder if we will still have releases, or if a "git pull" will do the job :-)
If you like the new branch, please set the ticket to positive_review
.
Thaaaaaaaaaaaaanks !
Nathann
New commits:
400bdc1 | trac #15439: typo fixes |
4db468c | trac #15439: combinat.matrices.latin.isotopism should not use '*' on permutations |
comment:14 Changed 6 years ago by
Looks good and tests well. positive_review is right. Thanks!
comment:15 Changed 6 years ago by
Thaaaaaaaaaanks !
Nathann
comment:16 Changed 6 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:17 Changed 6 years ago by
- Reviewers set to Darij Grinberg
comment:18 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:19 Changed 6 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Hellooooooooooooooo !!!!
1) I did not know what an isotopism was either, and it looks like we could add a link toward the following Wikipedia page if we patch this file : http://en.wikipedia.org/wiki/Latin_square#Equivalence_classes_of_Latin_squares
2) "Morally", this '*' can be any of the two actions, as it should only apply to permutations with disjoint supports : this part of the function builds a permutation from a 'cycles notation', i.e.
'(1,2,3)(4,5)'
. It builds a permutation for each cycle and multiplies the results, so both actions should be fine.3) Morally, this part of the code is made for disjoint cycles notations, but nothing actually checks that. And given a permutation in cycle notation (as a string)
'(1,2,3)(4,5)'
, don't you have the very same problem knowing in which order they should be applied ? Or is that clear for everybody ? I honestly ask the question, I personally always used permutations like function composition, and all that happens with this left/right action is beyond me:-P
4) This code has *NOTHING* to do there. Its only purpose is to accept any kind of permutation input on 0..n-1 and to output a permutation on 1..n. It's like this code should appear in the constructor of
Permutations
, with a flagtranslate_from_0n_to_1n=True
5) Having something like
Permutations.global_options
which redefines the meaning of'*'
is *criminal*.Nathann