WikiProject Mathematics | (Rated B-class, High-priority) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
1 |
Sections older than 12 months may be automatically archived by Lowercase sigmabot III. |
Major Problem with Notation
If I am not mistaken (mistakenness is always possible) there is a huge split in the way people write permutations.
A mere notational divergence in itself would not be a big deal. There are many different kinds of notations used to describe many different mathematical objects. Generally they can portray and let portray. A mixed situation may not be ideal, but it is certainly no catastrophe.
What (I claim) makes the split in permutation notation rather more serious is that the two kinds of notation are indistinguishable, yet mean different things. In fact, we have not two different notations, but two different interpretations of the same notation. This confuses and disturbs me.
I speak, of course, of the popular double-line notation (or, equivalently, the single-line notation) for specifying a permutation. One group of practitioners uses a sequence of numbers to refer to positions in the permutation. I will call this the Address Method. The other group uses a sequence of numbers to refer to the values contained in those positions. I will call this the Value Method.
An example follows.
1 2 3 4 5 | | | | | 3 5 1 2 4
Suppose one sets out to use the above-notated permutation to reorder the sequence {5, 2, 4, 3, 1}.
Here is what happens when one applies the two different interpretations.
Using the Address Method, we understand the second line to be a picture of the first line after it has been operated on by the permutation. Thus we interpret the permutation to direct us as follows: "send the contents of position 3 to position 1; send the contents of position 5 to position 2; send the contents of position 1 to position 3; send the contents of position 2 to position 4, and send the contents of position 4 to position 5.
The result is {4, 1, 5, 2, 3}.
Using the Value Method, we understand the second line as a mapping of the values in the first line. Thus we interpret the permutation to direct us thus: "change each 1 to a 3, each 2 to a 5, each 3 to a 1, each 4 to a 2 and each 5 to a 4."
The result is {4, 5, 2, 1, 3} --- entirely different from the result of using the Address Method.
This same split is, amazingly, also present in Cycle Notation, where, for example, the cycle {1, 2, 5} may again refer to addresses or to values. The results then differ just as they do when applying double-line notation.
As far as I know, both systems produce working models of, say, a Symmetric Group. The problem lies not in any failure of theory, but only in a failure to produce the same written results from the same starting materials. I would hope such a problem would not affect people trying to grasp the rudiments of group theory by studying Wikipedia. (No, Wikipedia is not an ideal textbook, but it may very well serve as such for a while in some circumstances. And if it is useless, what's the point of writing this stuff?)
I am not neutral on this point. I favor the Address Method. I have several (I think) compelling reasons for that preference, but in order to keep this message short, I will save the details for a continuing exchange.
The Value Method is in use in the article under discussion here, namely Permutations. In the case of this particular article, changing the notation would require some rewriting, since there are verbal descriptions associated with the Value Method.
Already breaking my promise to wait before making an argument, I offer here one reason to consider changing the notation in the article. Consider the results below, copied from a Mathematica session.
?Permute Permute[expr, perm] permutes the elements of expr according to the permutation perm. In[1]:= Permute[{5,2,4,3,1},{3,5,1,2,4}] Out[1]= {4, 1, 5, 2, 3}
And Mathematica is far from the only reason to consider a change.
I am discussing this here because I am reluctant to jump in and make (what seem to me) significant edits without consulting the community. Please help me by following up on this.
Thank you Dratman (talk) 00:56, 26 August 2011 (UTC)
- Yes, there is an inherent and unavoidable ambiguity with one-line, two-line and cycle notations for permutations. (Though in my experience, I think the problem does not exist "in the wild" for cycle notation -- I've never seen anyone use cycle notation to represent moving addresses, rather than values.)
- First look at http://www.scientificamerican.com/media/inline/2008-07/puzzles/m12.html
- and then at http://www.scientificamerican.com/article.cfm?id=the-cycle-notation-and-m12 . This puzzle illustrates why the "address" method makes more sense, if not everywhere (though I think so), at least in a number of familiar situations. Think about the Rubik's cube. Do you describe moves as functions of color?
- For anther, independent example, see http://mathcircle.berkeley.edu/BMC3/perm/node3.html
- Dratman (talk) 18:39, 26 August 2011 (UTC)
- This is equivalent to the problem of whether we multiply permutations on the left or right. In fact, the two possible conventions are interchangeable by taking inverses of permutations (which exchanges values and positions, as well as the order of multiplication). It really doesn't seem possible to make a compelling case that one of these notations is preferable, since they literally carry exactly the same information and the use of both is widespread.
- I think in this situation that the sensible thing to do to preserve consistency of notation throughout as the main goal. This suggests to me that mucking around with the notation is a bad idea.
- Incidentally, the Mathematica description seems to me to be compatible with both notations because of the ambiguity about whether "according to the permutation perm" means that perm acts on the left or the right. --Joel B. Lewis (talk) 02:17, 26 August 2011 (UTC)
- Yes, there exist different conventions for what is meant by permuting (more than two conventions, as will be clear below), but the description of the problem by Dratman is confused. One thing there is NO confusion about is which permutation (in the sense of a bijection) is meant by a two-line notation or by a cycle notation: it is the map that sends any value in the first line to the value directly below it in the second line, respectively that sends any value in a cycle notation to the next value (wrapping to the start of the cycle if necessary).
- Also, in case the two-line form is reduced to a single line (as is done in the discussion above) then this is only done in case of permutations of a set [n]:={1,2,...,n}, and the reduction is then obtained by writing the two-line form with "1 2 ... n" as first line (as is most common, though not obligatory for a two-line form) and then dropping that first line.
- The next thing to worry about is composing permutations: here indeed there are two schools (see Permutation#Product and inverse). What I've seen most, and this article uses, is the convention that permutations compose as functions (which they are) do, so f∘g denotes the map x↦f(g(x)), in other words the permutation on the right "sees the argument first". The other school prefers the opposite order, and has the left permutation see the argument first; this would be natural is functions were written to the right of their arguments, but I don't think adherents of that school would normally do that (for one thing Knuth composes permutations left-to-right while writing functions to the left; this would give a mess when permutations are used as functions, but I guess he simply never does that). But I don't think this dichotomy is what Dratman asks about, so I will assume the right-to-left composition convention to get this issue out of the way.
- I "prefer" the right-to-left convention when I write f(g(x)). That notation is unambiguous! I prefer the left-to-right convention when I write A ∘ B, as in group theory (where it is disputed) or in the "syntactic sugar" first layer parser of any non-Lisp-type computer language (where it is not disputed). I am well aware that many people are strongly in favor of using the right-to-left convention everywhere. But the problem, I repeat, is not that there are two conventions. The problem, which (I claim) is serious, is that they are indistinguishable.Dratman (talk) 19:17, 26 August 2011 (UTC)
- Finally, and most to the point, there is the question about what permuting, or acting by a permutation, means. There are many sets that a permutation group can act upon, and the action could be defined in a arbitrarily complicated way. However there are two classes of "natural" ways for permutations to act: for sets "built-up" from [n] (such as [n] itself, or the set [n]2 of ordered pairs, or the set of k-combinations taken from [n]), the natural action is to apply the permutation (as a function) to each of the components; this is the "value" point of view signalled above. There is little confusion about this kind of action: one gets a left action by applying the permutation itself (rather than its inverse). In symbolic notation this action, in the case of [n]2, looks like
- .
- Finally, and most to the point, there is the question about what permuting, or acting by a permutation, means. There are many sets that a permutation group can act upon, and the action could be defined in a arbitrarily complicated way. However there are two classes of "natural" ways for permutations to act: for sets "built-up" from [n] (such as [n] itself, or the set [n]2 of ordered pairs, or the set of k-combinations taken from [n]), the natural action is to apply the permutation (as a function) to each of the components; this is the "value" point of view signalled above. There is little confusion about this kind of action: one gets a left action by applying the permutation itself (rather than its inverse). In symbolic notation this action, in the case of [n]2, looks like
- But in practice the other natural class of actions is more important: the actions on sets of the form Xn, i.e., of n-tuples taken from some set X, or on invariant subsets thereof. The action is by permuting the positions, so that each component of the n-tuple becomes a component of the result, at a position determined by the permutation. If one wants a left-action of the permutation group, then a permutation σ will send a component at position i to the position σ(i). While there is no inverse in this description, it will be present in a symbolic notation, which looks as follows
- ,
- because to know the first component of the result, one must search for a component that is sent to the first position, and that is the one originally at position σ−1(1). I am personally comfortable with this way of interpreting permuting of n-tuples, but one could prefer (maybe in view of the somewhat awkward symbolic notation) to define a right-action instead: then permutation by σ will send a component at position σ(i) to the position i, and in symbolic notation one gets (writing the permutation at the right, as is appropriate for a right action)
- ;
- this is I guess what is called the "Address Method" above (which reads the two-line notation from bottom to top: "send the contents of position 5 to position 2" (because 5 is below 2)). I also suppose this is what Mathematica does, which example would have looked much clearer if it had been given as follows (but it is just my guess that Mathematica would do this, as I don't have it to try; also I find the braces particularly disturbing since normally order is ignored inside a set):
- But in practice the other natural class of actions is more important: the actions on sets of the form Xn, i.e., of n-tuples taken from some set X, or on invariant subsets thereof. The action is by permuting the positions, so that each component of the n-tuple becomes a component of the result, at a position determined by the permutation. If one wants a left-action of the permutation group, then a permutation σ will send a component at position i to the position σ(i). While there is no inverse in this description, it will be present in a symbolic notation, which looks as follows
In[1]:= Permute[(e,b,d,c,a),{3,5,1,2,4}] Out[1]= (d, a, e, b, c)
- Yes, that is exactly the result given by Mathematica.
- Sadly, Mathematica uses "{...}" as list delimiters, to enclose any non-atomic object whatsoever. It is definitely not set notation.
- That bothered me until I realized it's just like Lisp's "(...)": the language has no grammar below that level, so one set of delimiters has to be universal. Dratman (talk) 18:00, 26 August 2011 (UTC)
- This is consistent with the fact that the Permute function takes the permutation as its second (right) rather than its first (left) argument.
- If one wants to act on the set P of "permutations in one-line form", namely the set of n-tuples with n distinct components taken from [n] , then one finds oneself on the intersection of the two classes: P is both built-up from [n], and an invariant (under permuting) subset of [n]n. So this is the most confusing case possible, where several "natural" actions of permutations compete (it would have been different if n-tuples with n distinct components taken from any other n-element set were considered, in which case only permutation of positions would be possible). So we have (at least) three such ways to act by a permutation σ on a one-line form p: two left actions which are (1) apply σ to each component (the Value Method), and (2) send each component at position i to the position σ(i) (the "left Address Method"), and one right-action (3) send (x1,...,xn) to (xσ(1),...,xσ(n)) (the "Address Method"). Denoting the fact that p is the one-line notation for a permutation π as p=ol(π), these three methods can also be described as sending this ol(π) respectively to (1) ol(σ∘π), to (2) ol(π∘σ−1), and to (3) ol(π∘σ). I think the real root of confusion is that in the very particular case that p=(1,2,...,n) (so π is identity), the results of (1) and (3) are the same (though the actions are quite different) since σ∘π=π∘σ when π is identity. So saying that σ is the permutation that sends p=(1,2,...,n) to ol(σ) does not tell you whether left-action (1) or right-action (3) were used. Moral: it is a bad idea to think of permutations as defined by the way they transform one-line forms;
- Exactly. That is how this ambiguity came into existence. One should not define a function of certain positive integers as "(4, 7, 2, 1, 8)" when one means f(1) = 4, f(2)= 7, f(3) = 2, f(4) = 1, f(5) = 8. Use any notation you like, but make it clear what you mean Dratman (talk) 19:47, 26 August 2011 (UTC)
- they are just bijections [n]→[n], and as such there is no ambiguity. And the definition of the two-line notation uses the Value Method, since the permutation used throughout the example above could be written not only as
- If one wants to act on the set P of "permutations in one-line form", namely the set of n-tuples with n distinct components taken from [n] , then one finds oneself on the intersection of the two classes: P is both built-up from [n], and an invariant (under permuting) subset of [n]n. So this is the most confusing case possible, where several "natural" actions of permutations compete (it would have been different if n-tuples with n distinct components taken from any other n-element set were considered, in which case only permutation of positions would be possible). So we have (at least) three such ways to act by a permutation σ on a one-line form p: two left actions which are (1) apply σ to each component (the Value Method), and (2) send each component at position i to the position σ(i) (the "left Address Method"), and one right-action (3) send (x1,...,xn) to (xσ(1),...,xσ(n)) (the "Address Method"). Denoting the fact that p is the one-line notation for a permutation π as p=ol(π), these three methods can also be described as sending this ol(π) respectively to (1) ol(σ∘π), to (2) ol(π∘σ−1), and to (3) ol(π∘σ). I think the real root of confusion is that in the very particular case that p=(1,2,...,n) (so π is identity), the results of (1) and (3) are the same (though the actions are quite different) since σ∘π=π∘σ when π is identity. So saying that σ is the permutation that sends p=(1,2,...,n) to ol(σ) does not tell you whether left-action (1) or right-action (3) were used. Moral: it is a bad idea to think of permutations as defined by the way they transform one-line forms;
1 2 3 4 5 | | | | | 3 5 1 2 4
- but also (as is allowed, see Permutation#Notation) as
5 2 4 3 1 | | | | | 4 5 2 1 3
- (the same columns in a different order). You'll see that its second line is now obtained from the first one only by the Value Method, not by the Address Method. I hope this settles your question. Marc van Leeuwen (talk) 10:24, 26 August 2011 (UTC)
- In my experience, the majority of people who study finite permutation groups use action on the right, that is gh maps x onto h(g(x)). Zerotalk 11:29, 26 August 2011 (UTC)
- Whether or not you're right about the majority of people, I think the proper way to say this is defining composition so that the natural action of permutations on the base set [n] is a right action, although it is written on the left (personally I find using that combination of conventions somewhat masochistic). But that action is not the main topic of the initial question, which is about permutation actions (however changing the convention about composition does make everything one says about actions come out differently, which is why I wanted to fix composition first). Marc van Leeuwen (talk) 12:25, 26 August 2011 (UTC)
See also: Talk:Cayley_graph#Order_of_compositions
There the conclusion was, that ab stands for first do a, than do b, because that's how function composition is written by almost everyone. The article f.c. states the same. Watchduck (talk) 12:31, 26 August 2011 (UTC)
- Grmpf... even more confusion. Quoting from function composition:
- Thus one obtains a composite function g ∘ f: X → Z defined by (g ∘ f)(x) = g(f(x)) for all x in X. The notation g ∘ f is read as "g circle f", or "g composed with f", "g after f", "g following f", or just "g of f".
- Now where in that sentence does it suggest the the left factor g in the composition gets applied before the right factor f?? Also the Cayley graph talk page and article are somewhat confusing: in the article it says "For any the vertices corresponding to the elements and are joined by a directed edge of colour " but in the illustration there is an edge between (for instance) a node labelled 'a' and one labelled 'ba' (or 'cb' and 'bcb' in another illustration) which I cannot get by any sensible values for g and s in the cited sentence. And this problem is independent of how one defines elements of the group to act.
- To mitigate what I said before a bit, one can without too much confusion define the product permutation g.h as h∘g (apply h after g), provided one takes care to always distinguish 'dot' (or juxtaposition) from 'circle' (probably never using the latter), and to avoid writing g(x) (using something like x.g or xg instead for "the image of x by g"). Marc van Leeuwen (talk) 14:42, 26 August 2011 (UTC)
Grmpf ... sorry, I meant to write: "that ab stands for first do b, than do a"
In short: h∘g = h after g = h(g(identity))
Everything else seems to be very unusual, and should just be mentioned, but not used in the article. Watchduck (talk) 15:07, 26 August 2011 (UTC)
- Let me amend my comments to note that I agree with Marc van Leeuwen that I don't think the ambiguity for two-line notation exists in the wild, either, except to the extent that it's equivalent to the ambiguity about which side we multiply permutations on. I also would like to reiterate my opinion that it's a very bad idea to try to change the notation in the article. --Joel B. Lewis (talk) 19:43, 26 August 2011 (UTC)
I believe I have shown that both interpretations can, in fact, be found "in the wild." In case you missed the evidence, please see a reply I added, including 3 URLs, near the top of this section. Nevertheless, since several people here are strongly opposed to the idea, it appears we should not change the notation used in the article. Next question: can we clarify any ambiguities without excessively disturbing the flow of the article? I would like to ensure that a reader new to this area of math knows exactly which algorithm is intended. That should not be difficult to do. We just need to add a few definite indications as to how the method works, such as f(1) =, f(2) =, and so forth, along with some related indications of what, specifically, is supposed to happen. It would, however, be absolutely necessary to decide whether, in this article, permutations operate "on the right" or "on the left" -- a question about which there seems to be a good bit more uncertainty. Dratman (talk) 23:13, 26 August 2011 (UTC)
- I think that what is exactly meant by "both interpretations" has not been clearly indicated, which makes discussing difficult. However, having looked at the examples given, I'm understanding better the point of view that causes difficulty with the text of the current article. It is vital to make a clear distinction between a "permutation" (a bijection of a set to itself) and the act of permuting an n-tuple. One can discuss permutations without considering the act of permuting; most of the current article does that. On the other hand one can be interested in acts of permuting but not in considering bijections of a set; when studying the Rubik's cube one would be in such a situation, and the cited texts from the Scientific American and Berkeley take this point of view. I think the original question was posed from the latter "permuting" perspective, although it is not explicitly mentioned. In any case, from this perspective any permutations considered would be bijections on the set of positions (not of the values sitting in those positions, for instance colours in the case of Rubik's cube) so this is an Address interpretation of permutations.
- As I have mentioned above, there are two possible ways to associate an act of permuting to a given permutation σ: what I called (2) above, which sends the contents of position i to position σ(i), and (3) which takes the new value of position i to be the old value of σ(i); from the permuting perspective the question is in the opposite direction of associating a permutation to an act of permuting, but the two possibilities are still present. From the given examples I conclude that in popular texts (2) is most used, and this is psychologically understandable (σ goes in the direction of the movement of objects), so I'll stick to this convention. However in the permuting perspective one is not even really interested in associating a permutation to an act of permuting, but just to have a notation to write down that act. A natural choice, clearly made in the Scientific American, is to write down the result of permuting an standard initial n-tuple , (1,2,...,n). Now the sad fact of life is that the result of permuting (1,2,...,n) according to σ is not the second line of the two-line notation for σ, but of that of its inverse. So this convention uses an alternative "one-line notation" for σ that is not related to the two-line notation for σ by taking the second line. One can get this alternative notation by reordeing the two-line form so that its second line is increasing, and then taking the first line. The confusing comes in part from the fact that this convention is seldom made explicit. Maybe this is the reason that mathematical texts hardly ever introduce the one line form for permutations, it is too confusing.
- However I restate: there is no ambiguity in the meaning of the two-line or cycle notations as designating a bijection (please prove examples if you contest this). So this article can stay as it is, maybe adding a note about permuting. Marc van Leeuwen (talk) 06:00, 30 August 2011 (UTC)
- I now agree that the article should not be changed, except possibly to clarify (briefly and unobtrusively) exactly what the manipulations used in the article mean and what they specifically do.
- With respect to any more real-world ambiguity in the use of the two-line or cycle notations as designating a bijection, my question has always been, DO they refer to a bijection, and exactly how is such a bijection being specified? To this I now want to add the question, do they refer to a "left action" or to a "right action"? These details are all relevant when one tries to work out examples. I will present any additional findings after further study.
Here is another typical instance of the problem, from Mathworld:
- A permutation cycle is a subset of a permutation whose elements trade places with one another. Permutations cycles are called "orbits" by Comtet (1974, p. 256). For example, in the permutation group , (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering [1,2,3,4], the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., 1->4->3->1.
Here the author unambiguously uses the notion of moving items from one position (what I've called a slot) to another, but then unfortunately starts from [1,2,3,4], from which both methods have the same effect! Dratman (talk) 04:38, 20 November 2011 (UTC)
- In trying to learn how to convert 2-line to cycle notation, it was not obvious that (by definition) an application of a k-cycle must change the positions of all k of its elements. Talking instead of editing in case I overlooked its mention elsewhere. Also, does this imply that k-cycles always have sign of (-1)^(k-1)? — Preceding unsigned comment added by 74.129.169.64 (talk) 15:33, 8 April 2018 (UTC)
I would like to add that the Mathematica examples above might be misleading.
By default Permute[{5,2,4,3,1},{3,5,1,2,4}]
= {4,3,5,1,2}
and Permute[{e,b,d,c,a},{3,5,1,2,4}]
= {d,c,e,a,b}
.
Only when the Combinatorica package is used (Needs["Combinatorica`"]
) it changes to the cited results {4,1,5,2,3}
and {d,a,e,b,c}
.
At least these are the results I got in a trial version of Mathematica Online.
I have created v:Permutation notation to come to terms with the problems described in this section. There is also a section on Wolfram. --Watchduck (quack) 23:07, 6 December 2016 (UTC)
Recent edits
I've spent some time renovating the article. But I think I'll stop here to give everyone else a chance. There is still some duplicated content in the article and I'd like to excise the section "Other uses ..." since it isn't about permutations per se and is likely to confuse the reader. ImTheIP (talk) 14:40, 29 October 2018 (UTC)
- While I'm generally happy with the edits you've been making, a word of caution is in order. It seems clear to me that you are writing for a mathematical audience with an occasional nod toward other readers. This may cause problems. Consider some of the remarks given earlier on this talk page. There was a time when "a permutation is a bijection" did not even appear on the page and you are moving in the direction of turning that on its head. Several readers come to this page only with the elementary concept of arrangement and a confusion between permutations and combinations; talking about bijections will not help these folk. I think a balance has to be struck between the mathematically correct and the historically useful approaches to the topic. I would definitely not excise the "Other uses ..." section since it is only "not about permutations" from only one point of view. Also, please be a little more careful in proof-reading. Most of my corrections have been fixing blatant errors and I'd be happy to discuss my reasons for any more substantial changes. --Bill Cherowitzo (talk) 23:46, 29 October 2018 (UTC)
- I share this concern. In particular, it is not universally true that a permutation is a bijection: it is true-ish in the context of modern research mathematics, but not in the historical usage of the term nor in its current usage in some elementary contexts. Even in the modern setting it is not necessarily true that a permutation is a bijection: in many contexts a permutation is actually a word or actually a matrix, for example. (Of course these things are naturally in correspondence with each other, but it is not true that one of them is uniquely privileged over the others.) --JBL (talk) 10:29, 30 October 2018 (UTC)
- I don't think that anyone is advocating removing bijective functions from the discourse, and if you got that impression from my comments, that's my bad! What I am advocating is raising the level of the passive interpretation of permutations so that it is comparable to the group theoretic approach (which your edits have clearly improved). The old first paragraph made a reasonable attempt to do this and I will put that back in along with some other tweaks to bring more of a balanced view to the article.--Bill Cherowitzo (talk) 17:48, 31 October 2018 (UTC)
What is the idea behind having some books in the Further reading list and others in the Bibliography? ImTheIP (talk) 13:56, 5 November 2018 (UTC)
- According to WP:FURTHER and Wikipedia:Further reading sources that are not directly used as references, but for which some editors feel are still valuable resources for readers, should be put in a Further reading section. I find this guideline particularly useful in keeping down the clutter when Harvard style referencing is being used. --Bill Cherowitzo (talk) 19:31, 5 November 2018 (UTC)
Edit request
After being informed by MrOllie about a potential conflict of interest, I am now formally requesting to make the following additions to the page. The Combinatorial Object Server is a collection of open source software tools I frequently use to create this kind of illustrations, and to which I am a frequent contributor.
Extended content
|
---|
A: Add the following paragraph to the Subsection "Generation with minimal changes": The following figure shows the output of all three aforementioned algorithms for generating all permutations of length , and of six additional algorithms described in the literature. 1: Lexicographic ordering; 2: Steinhaus-Johnson-Trotter algorithm; 3: Heap's algorithm; 4: Ehrlich's star-transposition algorithm (see [2]): in each step, the first entry of the permutation is exchanged with a later entry; 5: Zaks' prefix reversal algorithm[3]: in each step, a prefix of the current permutation is reversed to obtain the next permutation; 6: Sawada-Williams' algorithm[4]: each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries; 7: Corbett's algorithm[5]: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position; 8: Single-track ordering[6]: each column is a cyclic shift of the other columns; 9: Single-track Gray code[6]: each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions. B: Add the following external link: References
|
Torsten Mütze (talk) 19:07, 29 May 2019 (UTC)
- Per my concerns at the bottom of Talk:Gray code (Special:PermanentLink/899583820#tbf-objection-2019), I object to the addition of the external link (B). I have no opinion on part A. ~ ToBeFree (talk) 23:45, 30 May 2019 (UTC)
- If this edit is done, I would change "Steinhaus-Johnson-Trotter" to "Steinhaus–Johnson–Trotter" (with an en-dash rather than a hyphen), per WP:MOS, and where it says "red=1" I would instead write "red = 1" (and similarly with the other colors, of course), since that is the standard format.
- Contrast:
- Steinhaus-Johnson-Trotter
- Steinhaus–Johnson–Trotter
- red=1
- red = 1
- Michael Hardy (talk) 21:16, 31 May 2019 (UTC)
- Done All proposed edits and suggested modifications for (A) have been implemented. The proposed additional links to the EL section (B) were declined. Thank you to everyone for their input. Regards, Spintendo 15:59, 9 June 2019 (UTC)
Permutations with repetitions
In permutations with repetitions it has to be stated at least Tuple#n-tuples_of_m-sets as the word tuples alone is only the plural of tuple (ordered set or list) so ordered sets or lists and permutations without repetitions refers to a scalar number
It has to be clarified Tuples at least as Tuple#n-tuples_of_m-sets as Tuples alone is only the plural of Tuple and Permutations without repetition is a scalar number. Orendona (talk) 20:42, 1 November 2020 (UTC)
- I see from your edits that you want to refer to the cardinality of the set of permutations with (or without) repetition. Is this the scalar number you mention above? This would be a very tortured way to approach the topic and demonstrates some deep confusion. --Bill Cherowitzo (talk) 21:56, 1 November 2020 (UTC)
That is the use, they are not tuples, they are a special kind of tuples: All the possible tuples that can be made with repeated or not members of a second set. And they are not permutations. Some of the tuples are permutations of others. Orendona (talk) 13:16, 3 November 2020 (UTC)
Add real notations in notation subtopic
Adding real notations in notation subtopic will help people new to this and it makes article more easy to read. Anish59312 (talk) 04:59, 13 July 2021 (UTC)
Confusing address and value
In the examples, slot numbers and values both use numbers, hiding the fact that the two are not the same. I propose that slots be identified by numbers, while values are letters. Comfr (talk) 16:50, 16 August 2021 (UTC)
Active and passive confusion in lede
When the lede moves from the intuitive notion of permutation as a rearrangement to the technical definition as a bijection, I'm afraid it just gives the passive "permutation", instead of properly constructing the function f that would actively perform the rearrangement, i.e. by moving the element i to the place f(i).
Specifically, the informal "permutation" which is the arrangement (3, 1, 2) of the numbers {1, 2, 3} should correspond to the function accomplishing this arrangement by putting element i into place , which implies and . The permutation presently given is actually the inverse, .
The preceding statement "This is related to the rearrangement..." suffers from the same confusion, on top of mistakenly "rearranging" an arbitrary (unordered) set S. I suggest that this sentence should be removed while a similar, corrected, explanation is adapted to the specific example and inserted into the following sentence. ––St.nerol (talk) 21:16, 16 September 2021 (UTC)
- There is no correction to be made here. There are two reasonable conventions for how to record a bijection from {1, ..., n} to itself as a sequence. I believe that the article is internally consistent in choosing the convention that the sequence corresponding to the bijection a is (the one-line notation). In my experience, this is also the convention overwhelmingly used by combinatorialists. It happens that you are using the other convention. --JBL (talk) 20:32, 17 September 2021 (UTC)
- @JayBeeEll: Not so fast! I'm aware of the ambiguity and I'm not really taking sides. (I agree we should use what's most common.) Carefully re-reading, I can very explicitly show how the lede is not consistent with the body, with the lede seemingly following an older convention. Please, hear me out.
- The Definition-section points out that the modern view is "a permutation is a function that performs the rearrangement [while] an older and more elementary viewpoint is that permutations are the rearrangements themselves. To distinguish between these two, the identifiers active and passive are sometimes prefixed." It is perhaps not entirely clear how "active" and "passive" are used here, but Wikiversity gives an explanation which is at least related: "an active permutation [...] moves an object from place to place ". Now, this is the exact opposite of what's described in the lede, in which "each element s is replaced by the corresponding f(s)". This is, instead, what Wikiversity describes as the passive convention.
- Now, the active permutation, as defined above, is clearly used in the section "Matrix representation". Consider the permutation , which can be read from the matrix according to the instructions σ(j) = i if Mi,j = 1. This gives , , , in one-line notation 3 1 2, and still, explicitly, . So is the permutation 3 1 2, which rearranges (1,2,3) into (2,3,1). This is just fine, provided the one-line notation is just a compact way of writing down the bijection as an active permutation.
- The two math books I've consulted are not so concerned about the interpretation as a rearrangement and just mention it in passing. But of course, it's sensible that Wikipedia starts out by introducing the arrangement (3,2,1) as a "permutation", before segueing over into the formal treatment. However in order to have the arrangement (3,2,1) simply correspond to the one-line permutation 3 2 1, I'm afraid we'd actually have to use the older, passive convention – throughout! (And I'm not suggesting that.)
- If you're not fully convinced, I'd at least ask for a clarify-tag at the sentence which begins "This is related to" and a dubious–discuss-tag at the following "For example". – St.nerol (talk) 19:04, 27 September 2021 (UTC)
- It seems to me that your quibble is with Wikiversity, not with Wikipedia. From a group-theoretic perspective, the symmetric group can act on words from both the left and the right; one of these actions permutes "by value", the other one permutes "by position". As long as you believe the group is a separate object from the words, you are taking the "active" perspective. By contrast, the passive perspective is that permutations are the lists (with no group structure). It is unfortunate that combinatorialists have not adopted a uniform "right-hand rule"-type approach that resolves, arbitrarily but unambiguously, the inherent notational ambiguities around these questions; nevertheless, the convention followed in the lead of this article is consistent with the convention followed in the body, and that's what matters. --JBL (talk) 20:16, 27 September 2021 (UTC)
- @JayBeeEll:
The convention used in the section "Matrix representation" in this article is inconsistent with the lede.–St.nerol (talk) 21:08, 27 September 2021 (UTC) - It seems, actually, that it is the instruction for reading the matrices that is wrong. The given (σ(j) = i if Mi,j = 1) is the row representation; the matrices (for it doesn't matter) are written in the column representation. This made me mistake the notation to mean the permutation acting upon ; it seems to mean just . –St.nerol (talk) 21:32, 27 September 2021 (UTC)
- I wrote the following thing while you were revising; I leave it here so I don't lose it, and will seek to address your new comment shortly:
At first glance, I don't think you are correct -- in that section, means that pi is the function such that pi(1) = 2, etc., just as in the introduction. (The second sentence of the section does seem dubious to me -- surely the convention being described involves multiplying the permutations in the opposite order of the matrices? -- but my impression is that's not your issue with it.) --JBL (talk) 21:52, 27 September 2021 (UTC) - Well, that section is rather weird, isn't it? The first paragraph says "you should do it in way X to get effect Y", but then the example does it in way not-X and we get not-Y (namely, the permutations and matrices multiply in the opposite order). ¯\_(ツ)_/¯ (But there's still no problem in the lead.) --JBL (talk) 21:58, 27 September 2021 (UTC)
- ...and all of a sudden a side point has become the main point! Right, and there seems to be more than one problem in that section. Please check again the matrix that's supposed to represent pi. Since 2 = pi(1) we should have M_{2,1} = 1. But instead we're given M_{1,2} = 1. –St.nerol (talk) 22:19, 27 September 2021 (UTC)
- Looking again, I'm not convinced that there is a "not-X not-Y"-problem. –St.nerol (talk) 22:24, 27 September 2021 (UTC)
- The first paragraph says, correctly, that if you define a matrix P_{pi} via P_{i, j} = 1 if i = pi(j) and all other entries are 0, then P_{pi} * P_{sigma} = P_{pi * sigma}. The third and fourth paragraphs use the opposite convention: they associate to each permutation pi the matrix (P_{pi})^(-1), correctly observe that with this (inverse) convention matrices and permutations multiply on opposite sides, and then do an example using this inverse convention (with the same one-line representation of permutations as in the lead section). There are no substantive errors here, but there is an unforgivable re-use of the notation M_pi to mean two inverse things, and no clear indication to the reader that two (incompatible) conventions are being used in close quarters. I haven't looked at the images (linked or displayed) to see how they fit in. --JBL (talk) 01:43, 28 September 2021 (UTC)
- I wrote the following thing while you were revising; I leave it here so I don't lose it, and will seek to address your new comment shortly:
- @JayBeeEll:
- It seems to me that your quibble is with Wikiversity, not with Wikipedia. From a group-theoretic perspective, the symmetric group can act on words from both the left and the right; one of these actions permutes "by value", the other one permutes "by position". As long as you believe the group is a separate object from the words, you are taking the "active" perspective. By contrast, the passive perspective is that permutations are the lists (with no group structure). It is unfortunate that combinatorialists have not adopted a uniform "right-hand rule"-type approach that resolves, arbitrarily but unambiguously, the inherent notational ambiguities around these questions; nevertheless, the convention followed in the lead of this article is consistent with the convention followed in the body, and that's what matters. --JBL (talk) 20:16, 27 September 2021 (UTC)
Mentioning that disjoint cycles commute in Cycle Notation section
The Cycle Notation section explains that many different cycle notations are possible for the same permutation because the starting point for each cycle can be any element in the cycle and then it goes on to give examples; however, the first example given, (125)(34)=(34)(125), is of two equivalent cycles whose order is commuted but whose starting points are unchanged.
This is doubly confusing because the article clearly states that permutations do not in general commute but does not mention that an exception to this general rule is when the permutations are disjoint.
My suggestion is either to move the (125)(34)=(34)(125) example to its own separate paragraph which explains that disjoint permutations commute and hence give rise to multiple cycle notations for the same permutation or to reword the current paragraph in line with my edit at 19:07, 21 January 2022. Obtuse Wombat (talk) 19:23, 23 January 2022 (UTC)
- The fact that disjoint cycles commute is important in its own right, separate from the fact that many cycle notations are possible. Its omission was a deficiency in the section, but it did not belong in the sentence where you stuck it. I have done a thing, hopefully it is agreeable. --JBL (talk) 19:50, 23 January 2022 (UTC)
- Separately, "rational" is an adjective, the noun you wanted is "rationale". --JBL (talk) 19:51, 23 January 2022 (UTC)
- Thanks JBL, your change is much better. And also thanks for the pointer to WP:BRD. Incidentally, I did think I was following a standard process based on the second sentence of the "Discuss edits" paragraph of How to use article talk pages, which I was led to via a Google search on "how to dispute reverts on a Wikipedia article". Obtuse Wombat (talk) 21:08, 23 January 2022 (UTC)
- @Obtuse Wombat: My edit summary was a snarky reaction, before I had taken the time to think about the content of your post here. I should have read and reflected for a moment first, before re-reverting and snapping. Sorry about that. --JBL (talk) 13:56, 26 January 2022 (UTC)
- Thanks JBL, your change is much better. And also thanks for the pointer to WP:BRD. Incidentally, I did think I was following a standard process based on the second sentence of the "Discuss edits" paragraph of How to use article talk pages, which I was led to via a Google search on "how to dispute reverts on a Wikipedia article". Obtuse Wombat (talk) 21:08, 23 January 2022 (UTC)
A nasty organization problem we need to fix
Here is the problem:
- Permutation#Permutations_without_repetitions contains the sentence: "In a similar manner, the number of arrangements of r items from n objects is considered a partial permutation. It is written as (which reads "n permute r"), and is equal to the number (also written as )"
- Permutation#k-permutations_of_n restates the same information, but with more detail: "A weaker meaning of the term permutation, sometimes used in elementary combinatorics texts, designates those ordered arrangements in which no element occurs more than once, but without the requirement of using all the elements from a given set...(discussion w/ link to Partial permutation#Restricted partial permutations) ...""
- Partial permutation#Restricted partial permutations complicates matters even more by stating: "Some authors restrict partial permutations so that either the domain or the range of the bijection is forced to consist of the first k items in the set of n items being permuted, for some k. In the former case, a partial permutation of length k from an n-set is just a sequence of k terms from the n-set without repetition. (In elementary combinatorics, these objects are sometimes confusingly called "k-permutations" of the n-set.)" TO MAKE MATTERS WORSE, THIS LINK TO THE PAGE k-permutation is a redirect to this article's Permutation#k-permutations_of_n
I hesitate to fix this problem myself, but my tentative plan is to delete the last sentence in Permutation#Permutations_without_repetitions, i.e., the one that begins,
- "In a similar manner ... (also written as )
Then I will go back to Partial permutation#Restricted partial permutations, and rewrite the sentence with the words "confusingly called".
Yours truly, Guy vandegrift (talk) 03:38, 24 January 2022 (UTC)
- @Guy vandegrift: Can you identify precisely what you think the nature of the problem here is? (It's not clear to me from the juxtaposed quotes + suggested edits.) The words "permutation" and "partial permutation" are used for several different but closely related concepts, so there's bound to be some overlap and there's also bound to be some inconsistency (because sources are not consistent in how they use these terms). Quite possibly our articles on these topics could be clearer about both the overlap and inconsistency, but I'm not sure how your proposed deletions help with that. --JBL (talk) 14:03, 26 January 2022 (UTC)
- @JayBeeEll: At the very least, we need to fix the fact that is introduced twice in the same article. Let me explain why this is confusing: It is common to skim an article before deciding whether to carefully read it. A superficial explanation at Permutation#Permutations_without_repetitions, followed by a more complete explanation at Permutation#k-permutations_of_n renders this difficult.
- I appreciate your hesitancy to delete the first mention of this formula, since there is a reason to bring this up early in the article. A perfectly acceptable solution would be add a sentence linking the first mention to the second. And, since such an edit is so easily reverted, I will perform that myself. After that, I just need to clean up the redirect at the other article. Guy vandegrift (talk) 17:54, 26 January 2022 (UTC)
"cycle type" vs "cycle structure"
Which term should be used to describe the type of a permutation in this article: "cycle type" or "cycle structure"? Both are common but Google gave 23,900 hits on my search for 'permutation "cycle type"' and 32,900 hits for 'permutation "cycle structure"', so on 6 August 2022 I edited the article to consistently use "cycle structure" (but mentioned that "cycle type" was also used). This edit was reverted, so I posted this talk page section to discuss the issue. Prior, to my earlier 30 July 2022 edit, this page confusingly used four terms to refer to the same thing ("cycle type" 3 times, "cycle structure" 1 time, "permutation type" 1 times, and "type" (by itself) 2 times). Based on the Google stats, I think it would be best to use "cycle structure" and mention "cycle type" as an alternative term. Even if we stick with the reversion to "cycle type", "cycle structure" should be mentioned as an alternative term. Obtuse Wombat (talk) 19:06, 7 August 2022 (UTC)
- Thank you for cleaning up the article; I agree that the prior state was confusing.
The search you describe does not answer the relevant question, because it doesn't indicate how the terms are being used. Personally, I would use both phrases, but with slightly different meanings: I think it is common to use the words "cycle structure" when speaking loosely but I think it is rare to write a formal definition of "cycle structure". So I would expect that most uses of "cycle structure" could be replaced with "cycle type" with no loss in meaning, but that the reverse is not necessarily true. (Obviously I am relying heavily on vibes here.) --JBL (talk) 20:07, 7 August 2022 (UTC)