Talk:Permutation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Mathematics (Rated B-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
High Importance
 Field:  Basics
One of the 500 most frequently viewed mathematics articles.

Major Problem with Notation[edit]

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).
If only that were the case -- if no confusion existed -- we could close this issue immediately, and I would merely be wrong. I would not mind! Dratman (talk) 19:02, 26 August 2011 (UTC)
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 fg denotes the map xf(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
.
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):
     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
     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 gf: XZ defined by (gf)(x) = g(f(x)) for all x in X. The notation gf 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 hg (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: hg = 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)

Proposed Merge[edit]

I believe that Cycle notation should be merged into this article, Permutation. First of all, the treatment of cycle notation in this article is more extensive that of its own article. The definition of cycle there is incomplete and the language used to describe the cycle decomposition is at too high a level for the topic. It would take major effort to bring that article up to snuff and in the end it would only be a repeat of what is already here. The only salvageable piece of that article is the example of S4 which I propose to merge here. Bill Cherowitzo (talk) 23:01, 10 April 2014 (UTC)

It probably makes sense to merge here, though it would be nice to have a top-level notation section devoted to notation of permutations. There may be scope for then splitting off the content of this section, or not, but even if it was split off, I'd think that it should deal with notation of permutations, not only with cyclic notation. The merge would serve to make the material cohesive and eliminate excess duplication. —Quondum 16:56, 7 June 2014 (UTC)
I think the cycle notation should be divorced from under the heading of Permutations_in_group_theory for it is used in other contexts too. The group theory part has interesting things to say about permutations in cycle notation (e.g. conjugates etc.), but it's not the only angle on cycle notation, e.g. Foata's transition lemma is practically never mentioned in group theory books. 86.127.138.67 (talk) 10:12, 4 April 2015 (UTC)
I also agree with the merge. I've added some material (here) on the conversion between notations. It would make little sense to add it to the short article because it doesn't define the one-line notation etc. 86.127.138.67 (talk) 09:38, 4 April 2015 (UTC)
There is one fly in the ointment concerning a merge which I object to very strongly. The original cycle notation article was in fact very informative. In addition, the talk/discussion tab contained some very informative discussion that clarified many of the main points of that article. Merging may be a reasonable idea, but the original page and talk/discussion should be included in the history of the Permutation article that the original cycle notation article has been merged into. As it stands now, the content of the original article and talk/discussion is completely disappeared (or at least inaccessible). For those of us who wish to refresh on it, this complete purging of the content is completely unfair. Please either restore the original article and talk/discussion or include it as part of the history of the Permutation article into which it was merged. At least this way, the original material is available to those of us who wish to review it occasionally. — Preceding unsigned comment added by 2602:306:BD4D:6920:21B:77FF:FE9D:A6DA (talk) 22:12, 27 December 2016 (UTC)

Annoyingly bad presentations in several books[edit]

Alas the stuff I've added is a bit less than satisfactory. Bona's presentation is somewhat confusing in that in his fascination with Foata's transformation he doesn't separately present the properties of the canonical cycle form. I thought I found a good fix to this by reading/using Aigner's book, but it also has problems. For example he says (p. 25):

Conversely, from any n-permutation a1a2 . . .an we may uniquely recover the cycle decomposition: (a1a2 . . .) (ai . . .)(aj . . .) . . ., where ai is the first entry larger than a1, aj is the first entry after ai larger than ai, and so on. Thus, the number of cycles determined in this way equals the number of left-to-right maxima of the word a1a2 . . .an.

The only problem with this is that there may be no ai greater than a1, e.g. if the one-line/word is 321 (Appologies for the lack of TeXing but I feel rather pissed right now and not in the mood for more formatting.) 86.127.138.67 (talk) 13:28, 4 April 2015 (UTC)

This is not a problem: "and so on" means you stop when you can't go on; if a1=n you stop with a single cycle. What's the problem?--JBL (talk) 13:38, 4 April 2015 (UTC)

So, how I can calculate the number (or position) of a given permutation?[edit]

If I got a permutations of the numbers 1…16, e.g. (10,4,8,11,3,16,9,6,14,1,15,7,2,13,5,12), how can I calculate efficiently the position of this permutation in the lexicographical-ordered list of all permutations from (1,2,3,…,14,15,16) to (16,15,14,…,3,2,1)? I can't get the algorithm from the formulae given in the article. :-( --RokerHRO (talk) 08:52, 19 August 2015 (UTC)

This page is not a help-desk. Try https://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics instead. --JBL (talk) 12:49, 19 August 2015 (UTC)

Unnecessary confusion caused by inconsistent notation[edit]

The section on other uses of the word 'permutation' explains k-permutation of n ″arrangements of a fixed length k of elements taken from a given set of size n" and I can only assume this refers to n number of items within a set being arranged into groups of length k.

Why, then, does the very proceeding section dealing with permutations with repetition refer to "arrangements of the elements of a set S of length n ... the set S has k elements" which seems to be referring to exactly the same basic mathematical concept (the number of groups of a given length from a fixed set of items) but is instead referring to k number of items being arranged into groups of length n. This strikes me as a pointless inversion and will only confuse readers further.

Can someone please explain why this is this way? I do not know enough about the underlying mathematics to comment on the correctness of the equations themselves in regards to one another.

Somerandompersonwithabrain (talk) 17:16, 13 February 2016 (UTC)

This topic has been around for a long time and has been frequently rediscovered in many disparate fields. The terminology is just not uniform due to that. We are supposed to be reporting on what is in the literature, and if that literature is inconsistent then so will our reporting of it be. If I were writing all of this stuff myself, as in a book or published article, then I could make the notation I use consistent. But the best we can hope for on Wikipedia is that we use the notations that are the most common in the literature, and this will lead to the problems you see. Trying to do otherwise will get shot down as being WP:OR.Bill Cherowitzo (talk) 22:39, 13 February 2016 (UTC)

The difference between Permutation and Combination[edit]

The difference between Permutation(NPr) and Combination(NCr) is as simple as that, in combination it is just that it is commutative but not associative. NPr - Permutation covers all the possibilities.

Commutative, Associative terms are generic in Mathematics,- Vector, Algebra, Linear Algebra and also Modern Algebra.

Dev Anand Sadasivamt@lk 05:55, 6 April 2016 (UTC)

Paren notation in intro is misleading[edit]

Hello, not a regular editor so I'll just post my concern here. In the intro it says "... there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1)."

The paren notation is misleading in this context. The remainder of the article clearly and correctly identifies the standard two-line mapping notation and the one-line cycle notation. Once a student has learned those, (1, 2, 3) is forever understood as cycle notation.

If someone is new to this material, the incorrect use of the parens is confusing and counterproductive to learning. Far better to use [1,2, 3] or <1, 2, 3> IMO. You don't need to explain this choice or call attention to it, since the intro is implicitly invoking the reader's intuition and they'll understand this just as well as with parens.

But later when they get to the two-line and cycle notations, they will not be confused by the earlier use of parens with a different meaning.

189.222.170.79 (talk) 04:36, 17 January 2017 (UTC)

In a perfect world everyone would use the same notations and ambiguity would never occur. Alas! While I personally only use the two forms you mentioned, I know that the one-line version is the preferred notation among computer scientists and some combinatorialists. This has a lot to do with how you are representing or using permutations. For these individuals, cyclic notation is useless and two-line notation is cumbersome. While your suggestions are good, they are not wide spread and Wikipedia only reports what is in the literature and does not try to "make things right". --Bill Cherowitzo (talk) 05:10, 17 January 2017 (UTC)

Recent edits[edit]

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)
Thanks for your critique! Personally I don't see how the permutation concept can be described without referencing bijective functions, but I'm open to ideas. Also, it is not my article so you can do the changes you see fit. ImTheIP (talk) 13:34, 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[edit]

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.

Ordering of all permutations of length generated by different algorithms. The permutations are color-coded, where 1=red, 2=yellow, 3=green, 4=blue.[1]

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

  1. ^ Mütze, Torsten; Sawada, Joe; Williams, Aaron. "Generate permutations". Combinatorial Object Server. Retrieved May 29, 2019.
  2. ^ Knuth 2005, pp. 1–26.
  3. ^ Zaks, S. (1984). "A new algorithm for generation of permutations". BIT Numerical Mathematics. 24 (2): 196–204. doi:10.1007/BF01937486.
  4. ^ Sawada, Joe; Williams, Aaron (2018). "A Hamilton path for the sigma-tau problem". Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. New Orleans, Louisiana: Society for Industrial and Applied Mathematics (SIAM). pp. 568–575. doi:10.1137/1.9781611975031.37.
  5. ^ Corbett, P. F. (1992). "Rotator graphs: An efficient topology for point-to-point multiprocessor networks". IEEE Transactions on Parallel and Distributed Systems. 3 (5): 622–626. doi:10.1109/71.159045.
  6. ^ a b Arndt, Jörg (2011). Matters Computational. Ideas, Algorithms, Source Code. Springer. doi:10.1007/978-3-642-14764-7.

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. Face-smile.svg Regards,  Spintendo  15:59, 9 June 2019 (UTC)