This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 |
I think there should be an example that clearly shows (visually) what a permutation is (such as the bells or the matrix in the abstract algebra section), before the section that tells one how to count permutations. Kevin Baas 17:29, 19 April 2004 (UTC)
Funny but I came to the article in order to check whether "permutation is the same as bijection" (at least for finite sets) and there is practically nothing on it... I actually thought it was the simplest way to define them? Pfortuny 17:11, 18 April 2004 (UTC)
This was cut from the article
Some of the older textbooks look at permutations in an alternative way. In computer science terms, they are defined essentially as assignment operations, with values
assigned to variables
Each value should be assigned just once.
There is here a real if subtle difference, illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition.
End of cut
Well, I disagree. I have taught students who have met this kind of definition, for example in Fraleigh's Algebra. It should be mentioned in this article, since it is a possible point of view on permutations. There is a problem, in my view, in taking the abstract algebra point of view as definitive. No doubt this point could be explained better; but it belongs on this page.
Charles Matthews 15:17, 19 April 2004 (UTC)
Sorry, Charles, I noticed you were the one who put in the comment about permutation being used "without qualification" as meaning a bijection. While I agree with you in principle, I think it's misleading. First of all, I took a combinatorics class in grad school, and we constantly used the term "permutation of r objects from a pool of n objects" or just "permutation" in this traditional sense all the time, usually saying things like "r-permute-n" or something. I admit, usually it's the bijection, but enough times it's used the other way that I don't see how it an be written off. Especially when this meaning is used extensively in one of the sections later on?? Revolver 22:51, 10 November 2004 (UTC)
---> The algorithm presented in this article doesn't work with set equal or less than 2. Explication are missing about it.
I heared that inversion occurs when an larger integer precedes a smaller one in a list. Is this in a context of combinations or abstract algebra? -- Taku 08:21, 19 November 2003 (UTC)
Can you give us an example? I don't understand exactly what you mean. Dysprosia 08:40, 19 November 2003 (UTC)
Obviously such inversions occur in any permutation, other than the one fixing each integer 1, ..., n. But I'd say that counting the inversions is more of a combinatorics topic.
Charles Matthews 10:00, 19 November 2003 (UTC)
Charles Matthews 07:21, 20 November 2003 (UTC)
In the interests of not starting an edit war, I'll make my points on the current state of the article instead, and leave it up to other editors to verify if they have merit or not.
Dysprosia 03:07, 28 March 2004 (UTC)
The sentence "Unlike a set, the order of elements is neccessary to record." is firstly poor English, and secondly incorrect. One has to specify the order of the elements of a permutation when defining it, but that is a property of the act of definition and does not specify what the permutation is. The sentence of Dysprosia is completely correct, but uses the word "significant" in the way mathematicians use it and so might not be understood by some readers.
The core of the issue is when two permutations are regarded as the same. For two sets to be the same it is necessary and sufficient for them to have the same elements. For two permutations, one must add in the same order. I propose to replace the disputed sentence by:
-- Zero 06:38, 28 March 2004 (UTC)
"signifigant" and "specified" and "matters" are words with no indirect object in the way you all have used them so far. NAMELY , its SIMPLY, precisely and ONLY the definition of permutation itself that makes the order "signifigant" or "specified" or "matter" i hate being repetitve, but this seems to be the only language you speak. i feel the current version is too verbose, more confusing than good and wasteful Hfastedge 03:05, 29 March 2004 (UTC)
its been changed Hfastedge 17:59, 31 March 2004 (UTC)
changed back by zero0000 without discussing http://en.wikipedia.org/w/wiki.phtml?title=Permutation&diff=0&oldid=3000993 Hfastedge 23:47, 31 March 2004 (UTC)
I think the page is pretty decent as it stands. Although it can be made more concise (as Hfastedge has suggested), I have no specific qualms. Regarding the words "significant" "specified" and "matter": words of this sort are important and neccessary for meaningful communication. "Significant" says that this information is what is relevant. "Specified" says that this information is established prior. "Matter" says that this information is important and has consequence. These are all very usefull words which convey a lot of information and operate on a single object/subject. (What is meant by "no indirect object"?)
In regards, "recording": this method may not be the best way to convey what a permutation is. It provides an extra level of indirection and extraneous concepts which may be confused with the subject. But it is not wrong in the respect that it implies an action. There is always action in mathematics - whether it's solving a differential equation or what have you. The formal set of rules in themselves may be purely logical and therefore devoid of action, but the choice of applying one rule over another to operate on a string (mathematical expression) is action, and mathematics does not - can not - exist independant of such action. Take for example a Turing machine - a Turing machine is neccesarily, regardless of how it is manifested, a dynamical system, and a dynamical system is neccessarily parameterized by a free paramater such as "time". The moment math becomes manifest - which is the momemt that it becomes meaningful - it is inextricably involved in action. Even as a concept it is involved in a dynamical system (the brain). Kevin Baas 19:55, 1 April 2004 (UTC)
Kevin's treatment is more intelligent and very complex. anyway, The verb to be. example sentances: the order is specified (by Whom, for what? WELL, BY the follower of the definition, FOR the purpose of following the definition)
the order matters/is signifigant (to whom? for what? WELL, to the follower of the definition most importantly.... any other reasons or people that it might matter to make this highly non-neutral, non scientific and subjective)
so i think the intro should go
from: In mathematics, in the most basic sense, a permutation is a sequence with no two elements the same. The difference between a permutation and a set is that the elements of a permutation are arranged in a specified order. This means that two permutations are regarded as the same only if they have the same elements in the same order
to: In mathematics, in the most basic sense a permutation is a sequence of elements chosen from a set such that no two elements are the same and that the order of elements is unique compared to all other permutations taken from the set.
better? Hfastedge 02:08, 5 April 2004 (UTC)
The bell ringing section doesn't seem to give precise definitions of "arrangement" and "substitution", at least it's not clear to me at all what these are supposed to mean? Can you elaborate?? Revolver 23:00, 10 November 2004 (UTC)
Einstein notation mentions "positive" and "negative" permutations and links here. This page doesn't discuss them. Can someone add a bit on that here and maybe a parenthetical there about this?
BenFrantzDale 15:07, 2 February 2005 (UTC)
I have a problem I've been trying to solve by encoding a repetitive permutation of three letters into one big number. It would look like this. AAA=1 AAB=2 AAC=3 ..... ABA=27 ABB=28 ABC=29 Is there a mathematical formula or algorithm for this?
A common modern notation is (n)r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol)
n(n + 1)(n + 2)...(n + r − 1).
In the latter case, the number of permutations is (n + r − 1)_r.
I found this passage confusing. The notation is introduced, not defined explicitly (except by implied equiv. to the previous result) and when the notation is defined in the same proximity, it's a contrary definition, plus the final formula surely can't be correct for the rising fact. notation, there must be a sign wrong. The casuaul reader could be easily mislead here. MaxEnt 09:52, 17 April 2006 (UTC)
I've seen other notation, specifically here [1], in the second question, and here [2] in questions 2iii and 2iv. Could someone who understands this a bit better than I do explain it, as it appears to be fairly common. 80.177.1.238 16:43, 8 March 2006 (UTC)
The section does not explain the notation for the identity perm in cyclic form. If all fixed points are omitted, one is lead to the conclusion that the notation for an identity perm. is an empty string. It also fails to point out an ambiguity where the last element is a fixed point (or tail suffix of such). You can't inspect cyclic notation with fixed points omitted to determine the number of elements in the perm. described, whereas without the omission of fixed points, the notation was entirely clear in both regards. MaxEnt 10:07, 17 April 2006 (UTC)
The "Abstract algebra" paragraph now seems obsolete and could be deleted, am I wrong ?
BTW, there's nothing wrong in defining a permutation of {1...n} once as a bijection from this set into itself, and once as a family (x1,x2,...,xn) of numbers from this set, each occuring once, since the two definition coincide (at least if we agree that such a family is indexed by {1,...,n}).
On the other hand there seems many many articles about the same subject, I try to start a non-exhaustive list:
I think they should be merged (urgently) or identified clearly (in each of the other articles) as the article treating a particular aspect of the thing (which should then not be discussed in any of the others). — MFH: Talk 22:53, 16 October 2006 (UTC)
And perhaps the solution method should be somewhere in the article. For example: The set {1, 2, 3, 4, 5, 6} has 720 different rearrangements (permutations of which n=6 and r=6). If the permutations were all put into matrices (in other words, if they were all in the matrix-esque display in the article), how many of them would apply to the following rules?: "s(x)=1, s(y)=2, s(z)=3, x<y<z" In other words, how many of these permutations would have the numbers 1, 2, and 3 in that order, including ones such as {6, 1, 2, 4, 3, 5} and {4, 1, 5, 2, 6, 3}? -Mr. Random
The algorithm presented in the article doesn't work with set equal or less than 2. Explication are missing about it.
in how many ways can the result of twelve soccer matches be arranged with either a win , draw or loss 41.210.20.124 ( talk) 18:12, 1 April 2009 (UTC)
The derivative page has five calculators in the external links and is rated higher than this page. Seems that makes for a better page. This is just not paper put to a Web page.
Warren Van Wyck ( talk) 01:40, 21 October 2009 (UTC)
I arrived planning to make the intro more layman-accessible, but now I'm confused myself. (Combinatoric) permutations can't use all the elements of the set? That's what I'm getting from "In combinatorics, the term permutation has a traditional meaning, which is used to include ordered lists without repetition, but not exhaustive (so of less than maximum length).". What would the, er, thingies 1,2,3, 2,1,3, and 3,2,1, taken from the set (1,2,3) be called, then? BTW, I'm a big proponent of putting a clear, simple example of a common case right up front so as to draw in the non-math types; I'll try to find a correct one once I figure out what's going on myself... Lunkwill 29 June 2005 07:38 (UTC)
The introduction is too long (WP:Lead). The historical information and quotation are obviously out of place. The remaining text should be trimmed down if possible. —Preceding unsigned comment added by NOrbeck ( talk • contribs) 20:35, 19 August 2010 (UTC)
In algebra and particularly in group theory, a permutation of a set S is defined as a bijection from S to itself (i.e., a map S → S for which every element of S occurs exactly once as image value). To such a map f is associated the rearrangement of S in which each element s takes the place of its image f(s). In combinatorics, a permutation of a finite set S is defined as an ordering of its elements into a list. In this sense, the permutations of S differ precisely by a rearrangement of their elements. For a set S that is given with an initial ordering, such as S={1,2,3,...,n}, these two meanings can be almost identified: applying a permutation in the first sense to this initial ordering gives an alternative ordering of the elements, which is a permutation in the second sense.
The term permutation is also used less formally to designate the act of rearranging parts of an object, or the result thereof. Thus one might define an anagram of a word as a permutation of its letters, or say that X3Y+7+Y2Z is (obtained by) a permutation of the terms of the polynomial X3Y+Y2Z+7. The act of permuting can also refer to substitution of symbols, for instance when saying that Y3Z+Z2X+7 is obtained from X3Y+Y2Z+7 by a (cyclic) permutation of the variables X, Y, Z. These statements can be given a precise meaning by considering an appropriate symmetric group action.
In combinatorics the second sense of "permutation" is sometimes broadened. In elementary combinatorics, the name " permutations and combinations" refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for k-permutations the order of selection is taken into account, but for k- combinations it is ignored. In fact counting k-permutations is used as a step towards counting the number of k-combinations, and also towards computing the number n! of permutations of the set (in either of the two meanings mentioned above). However k-permutations do not correspond to such permutations unless k = n, that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S, with a finite multiset M in which some values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M. Thus for M=[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M, but [3,1,2,1,2,3,1] is not.
Permutations occur, in more or less prominent ways, in almost any domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science. In algebra, an entire subject is dedicated to the detailed study of permutations, through the notion of symmetric group. The key to its structure is the possibility to compose permutations: by performing two given rearrangements in succession, the combination defines a third rearrangement.
The rule to determine the number of permutations of n objects was known in Hindu culture at least as early as around 1150: the Lilavati by the Indian mathematician Bhaskara II contains a passage that translates to
The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures. [1]
A first case where at first sight unrelated mathematical questions are studied with the help of permutations occurs around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. The development that came forth from this work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics there are many similar situations, where understanding a problem requires studying certain permutations related to it.
References
I have a feeling that there might be some statistical tests (say, nonparametric, just using ranks) that use facts from permutation.
A question, for example: If I draw from two distributions and order them in a single list, what is the probability that the observed permutation is at random (versus sufficiently disordered)? I know a Wilcoxon rank-sum test is a paired version. What about unpaired?
My point is it would be nice to work these references into the permutations article, or at least provide a cross-ref.
dfrankow ( talk) 21:16, 30 April 2009 (UTC)
Can you guys make thins simple to understand. Wiki pages on some topics are too obscure to understand. —Preceding unsigned comment added by 180.149.49.125 ( talk) 17:34, 19 March 2011 (UTC)
Could someone please re-mention the symmetry between decoding unique factoradic integer k for Permutations (Variable Bit Decoding) and Combinations (Constant Bit Decoding) since ite got nuked. Michael.Pohoreski ( talk) 17:02, 22 October 2010 (UTC) e.g. * http://en.wikipedia.org/?title=Permutation&oldid=342103380#Encoding_and_decoding
my calculator has a nPr button is this a common notation for purmutations? — Preceding unsigned comment added by 136.159.16.7 ( talk) 17:14, 22 September 2011 (UTC)
The lead section states in part:
Although this is mathematically correct, neither this nor the rest of the article make it clear to me for which n a permutation of a set of n objects is defined. I do not see any restriction on n in the article. I do not see n defined to be an integer, a natural number, etc. Specifically, does it make sense to speak of a permutation of an empty set? Would an expert on the subject of permutations please clarify these issues in the article? Thank you! — Anita5192 ( talk) 02:50, 28 February 2012 (UTC)
The illustration with the balls is kind of confusing. They should be separated so that the reader can see that the six sets are independent and not part of some sort of matrix of balls. — Preceding unsigned comment added by 71.239.6.227 ( talk) 02:58, 14 March 2012 (UTC)
Permutations is linked from cryptography pages, but it is not clear which definition applies. It would be nice if there was a more explicitate explanation of what a "permutation" is in the context of cryptography. 23.25.179.162 ( talk) 16:03, 3 October 2012 (UTC)
I have done extensive research on permutation and combination and found consistent result in my research. this result I have found is written in a book known as junction. To see my research result then log in to my sight https://sites.google.com/site/junctionslpresentation/home or e-mail me at Softlaws4095@gmail.com — Preceding unsigned comment added by 14.97.116.20 ( talk) 18:34, 24 April 2012 (UTC)
Now I have attached some microsoft word documents which gives some of the proofs of junctions on which I have done research. Please accept my research work this will enable for the convinient study of combination and permutation.
https://sites.google.com/site/junctionslpresentation/ — Preceding unsigned comment added by 27.5.177.192 ( talk) 14:50, 20 May 2012 (UTC)
The one in the article is by far the shortest I've come across. I've checked its outcome for various sequence lengths n, getting n! different arrangements each time, so conclude that it's valid. It would be nice if there was some explanation of the principle and a reference to its source. 86.132.234.4 13:31, 18 January 2007 (UTC)
It wasn't clear to me initially that the sequence index is 1-based, although looking at it now, the mathematical notation for the sequence does specify. Maybe this could be made clearer in the text? -- Lumimies 21:53, 1 May 2007 (UTC)
Yep pretty nice algo, many thanks for that. Using the factoradic on the fly is very good, I just pre-computed the factorial (from 1 to n) outside of the function to avoid recomputing at each call and zooooom...
I really think the algorithm should be changed to 0-based. Throughout other articles with array-processing algorithms, such as the Fisher–Yates shuffle, implementations are zero based. Zero-based arrays seem to very common in the field of computer science, and the algorithm should reflect that. I have attempted to change it on my own, but I have run into several bugs, especially when the length of the array given is 2. I think everyone would appreciate it if the algorithm was modified. Jessemv ( talk) 05:37, 20 November 2009 (UTC)
I was able to convert this algorithm to zero-based as follows: Have k run from 1 to n! inclusive. Then change the swap index calculation to s[k mod (j+1)], and have j run from 1 to (length(s)-1). The other swap index remains s[j] and the k update formula remains k/j (integer division with decimal truncation). Note you don't get the same permutations for the same values of k, nor is the order of permutations the same between these two versions. Let me know if you find an error or have a better zero-based index version. I don't have any bugs for s lengths of one or two with either version though. When I initially implemented this algorithm in C I made the mistake of not giving the algorithm the original s string for each value of k, so watch out for that. If you need an iterative permutation algorithm that gives the output in lexicographic order you can find one in the text Discrete Mathematics By Richard Johnsonbaugh. He also has source code posted here: http://condor.depaul.edu/~rjohnson/source/perm.c Qatux ( talk) 18:45, 20 November 2009 (UTC)
I tried using the algorithm to generate lexicographic permutations as described in this section. I was confused by the statement Since k + 1 is such an index, l is well defined and satisfies k < l in step 2 of the algorithm. It is true that l = k + 1 on the first permutation, but after the first permutation l can be equivalent to k + 2 or k + 3 ... etc. I thought having such a statement that is not applicable to all cases of permutation in the description of the actual algorithm was unnecessary and confusing. I added a walk through example of the algorithm in action as a contribution.-- James Lingford ( talk) 09:46, 7 August 2013 (UTC)
I recently converted the descriptor "sequence" for permutations to "ordered arrangement". This was reverted and I just re-reverted. My reasons for doing this are twofold. First, as I mentioned in my original edit, the term "sequence" is not quite correct, the proper term would be "sequence without repetition". If one were required to use this entire phrase, the appeal of this descriptor would soon vanish. One could say, early in the article, that for this article "sequence shall mean sequence without repetition", but this is a long article and readers do not always start at the top and read everything, so may fail to see that disclaimer. A further problem arises (and this is problem was never addressed) when permutations are applied to actual sequences and the term "sequence" had two meanings within the same sentence. Secondly, the term "sequence" is never used, outside of WP and its derivatives, except by a small cadre of computer scientists. The vastly predominant term is "ordered arrangement" and this can be found in high school texts, combinatorics texts and other elementary mathematics texts. By WP:Commonname this should be the term used in the article. We may or may not like the choice, but that is not our call to make. Note that in the later sections that deal exclusively with the computer science aspects of the topic, I left the sequence terminology in place with only a brief transitional comment about it. Bill Cherowitzo ( talk) 15:45, 9 June 2014 (UTC)
Article doesn't contain formula for case of permutations with repeated elements. http://www.vitutor.com/statistics/combinatorics/permutations_repetition.html
In some sources it denoted as variations with repetitions but Wikipedia seems to equate terms "variation" and "permutation". http://www.emathematics.net/combinavrepeticion.php LiberalDemocrat ( talk) 12:22, 28 December 2014 (UTC)
LiberalDemocrat ( talk) 10:53, 29 December 2014 (UTC)
Since participating at some length in this discussion four years ago, I've realized there is an even more fundamental problem here. The very first sentence of the article is as follows:
In mathematics, the notion of permutation relates to the act of rearranging, or permuting, all the members of a set into some sequence or order (...).
For a reader who knows the definition of set, this should fail to make sense. For a set has no initial order. A set is intrinsically unordered. How then can it be rearranged? It cannot be rearranged or, in common parlance, "permuted."
If for example you try to rearrange the set {pig, horse, duck} into, say, {horse, duck, pig}, you have merely shown an equivalent representation. Given that the notation {...} denotes a set, I insist without qualification that {horse, duck, pig} = {pig, horse,duck}.
If I must arrange the elements of a set, I am evidently forced to replace the set with an ordered tuple incorporating the same elements as the set. Thus the set {pig, horse, duck} must be replaced with a 3-tuple such as (pig, horse, duck), or (horse, duck, pig) before it can undergo a reordering operation. And as one more stroke of personal confusion, I find that I do not see how to specify a mapping between an arbitrary finite set and a tuple with the same number of elements as the set. For any specific set I can readily indicate such a mapping, but without having the elements of the set specified in advance, I am at a loss. Dratman ( talk) 00:26, 22 June 2015 (UTC)
Very good article. Very helpful. I commend you. — Preceding unsigned comment added by W1k13rh3nry ( talk • contribs) 23:58, 9 March 2007 (UTC)
— Preceding unsigned comment added by 201.255.142.74 ( talk) 22:23, 15 July 2009 (UTC)
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)
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)
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 Sadasivam
t@lk
05:55, 6 April 2016 (UTC)
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)
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)
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)
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)
In[1]:= Permute[(e,b,d,c,a),{3,5,1,2,4}] Out[1]= (d, a, e, b, c)
1 2 3 4 5 | | | | | 3 5 1 2 4
5 2 4 3 1 | | | | | 4 5 2 1 3
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 ... 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)
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)
Here is another typical instance of the problem, from Mathworld:
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)
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)
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)
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)
This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 |
I think there should be an example that clearly shows (visually) what a permutation is (such as the bells or the matrix in the abstract algebra section), before the section that tells one how to count permutations. Kevin Baas 17:29, 19 April 2004 (UTC)
Funny but I came to the article in order to check whether "permutation is the same as bijection" (at least for finite sets) and there is practically nothing on it... I actually thought it was the simplest way to define them? Pfortuny 17:11, 18 April 2004 (UTC)
This was cut from the article
Some of the older textbooks look at permutations in an alternative way. In computer science terms, they are defined essentially as assignment operations, with values
assigned to variables
Each value should be assigned just once.
There is here a real if subtle difference, illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition.
End of cut
Well, I disagree. I have taught students who have met this kind of definition, for example in Fraleigh's Algebra. It should be mentioned in this article, since it is a possible point of view on permutations. There is a problem, in my view, in taking the abstract algebra point of view as definitive. No doubt this point could be explained better; but it belongs on this page.
Charles Matthews 15:17, 19 April 2004 (UTC)
Sorry, Charles, I noticed you were the one who put in the comment about permutation being used "without qualification" as meaning a bijection. While I agree with you in principle, I think it's misleading. First of all, I took a combinatorics class in grad school, and we constantly used the term "permutation of r objects from a pool of n objects" or just "permutation" in this traditional sense all the time, usually saying things like "r-permute-n" or something. I admit, usually it's the bijection, but enough times it's used the other way that I don't see how it an be written off. Especially when this meaning is used extensively in one of the sections later on?? Revolver 22:51, 10 November 2004 (UTC)
---> The algorithm presented in this article doesn't work with set equal or less than 2. Explication are missing about it.
I heared that inversion occurs when an larger integer precedes a smaller one in a list. Is this in a context of combinations or abstract algebra? -- Taku 08:21, 19 November 2003 (UTC)
Can you give us an example? I don't understand exactly what you mean. Dysprosia 08:40, 19 November 2003 (UTC)
Obviously such inversions occur in any permutation, other than the one fixing each integer 1, ..., n. But I'd say that counting the inversions is more of a combinatorics topic.
Charles Matthews 10:00, 19 November 2003 (UTC)
Charles Matthews 07:21, 20 November 2003 (UTC)
In the interests of not starting an edit war, I'll make my points on the current state of the article instead, and leave it up to other editors to verify if they have merit or not.
Dysprosia 03:07, 28 March 2004 (UTC)
The sentence "Unlike a set, the order of elements is neccessary to record." is firstly poor English, and secondly incorrect. One has to specify the order of the elements of a permutation when defining it, but that is a property of the act of definition and does not specify what the permutation is. The sentence of Dysprosia is completely correct, but uses the word "significant" in the way mathematicians use it and so might not be understood by some readers.
The core of the issue is when two permutations are regarded as the same. For two sets to be the same it is necessary and sufficient for them to have the same elements. For two permutations, one must add in the same order. I propose to replace the disputed sentence by:
-- Zero 06:38, 28 March 2004 (UTC)
"signifigant" and "specified" and "matters" are words with no indirect object in the way you all have used them so far. NAMELY , its SIMPLY, precisely and ONLY the definition of permutation itself that makes the order "signifigant" or "specified" or "matter" i hate being repetitve, but this seems to be the only language you speak. i feel the current version is too verbose, more confusing than good and wasteful Hfastedge 03:05, 29 March 2004 (UTC)
its been changed Hfastedge 17:59, 31 March 2004 (UTC)
changed back by zero0000 without discussing http://en.wikipedia.org/w/wiki.phtml?title=Permutation&diff=0&oldid=3000993 Hfastedge 23:47, 31 March 2004 (UTC)
I think the page is pretty decent as it stands. Although it can be made more concise (as Hfastedge has suggested), I have no specific qualms. Regarding the words "significant" "specified" and "matter": words of this sort are important and neccessary for meaningful communication. "Significant" says that this information is what is relevant. "Specified" says that this information is established prior. "Matter" says that this information is important and has consequence. These are all very usefull words which convey a lot of information and operate on a single object/subject. (What is meant by "no indirect object"?)
In regards, "recording": this method may not be the best way to convey what a permutation is. It provides an extra level of indirection and extraneous concepts which may be confused with the subject. But it is not wrong in the respect that it implies an action. There is always action in mathematics - whether it's solving a differential equation or what have you. The formal set of rules in themselves may be purely logical and therefore devoid of action, but the choice of applying one rule over another to operate on a string (mathematical expression) is action, and mathematics does not - can not - exist independant of such action. Take for example a Turing machine - a Turing machine is neccesarily, regardless of how it is manifested, a dynamical system, and a dynamical system is neccessarily parameterized by a free paramater such as "time". The moment math becomes manifest - which is the momemt that it becomes meaningful - it is inextricably involved in action. Even as a concept it is involved in a dynamical system (the brain). Kevin Baas 19:55, 1 April 2004 (UTC)
Kevin's treatment is more intelligent and very complex. anyway, The verb to be. example sentances: the order is specified (by Whom, for what? WELL, BY the follower of the definition, FOR the purpose of following the definition)
the order matters/is signifigant (to whom? for what? WELL, to the follower of the definition most importantly.... any other reasons or people that it might matter to make this highly non-neutral, non scientific and subjective)
so i think the intro should go
from: In mathematics, in the most basic sense, a permutation is a sequence with no two elements the same. The difference between a permutation and a set is that the elements of a permutation are arranged in a specified order. This means that two permutations are regarded as the same only if they have the same elements in the same order
to: In mathematics, in the most basic sense a permutation is a sequence of elements chosen from a set such that no two elements are the same and that the order of elements is unique compared to all other permutations taken from the set.
better? Hfastedge 02:08, 5 April 2004 (UTC)
The bell ringing section doesn't seem to give precise definitions of "arrangement" and "substitution", at least it's not clear to me at all what these are supposed to mean? Can you elaborate?? Revolver 23:00, 10 November 2004 (UTC)
Einstein notation mentions "positive" and "negative" permutations and links here. This page doesn't discuss them. Can someone add a bit on that here and maybe a parenthetical there about this?
BenFrantzDale 15:07, 2 February 2005 (UTC)
I have a problem I've been trying to solve by encoding a repetitive permutation of three letters into one big number. It would look like this. AAA=1 AAB=2 AAC=3 ..... ABA=27 ABB=28 ABC=29 Is there a mathematical formula or algorithm for this?
A common modern notation is (n)r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol)
n(n + 1)(n + 2)...(n + r − 1).
In the latter case, the number of permutations is (n + r − 1)_r.
I found this passage confusing. The notation is introduced, not defined explicitly (except by implied equiv. to the previous result) and when the notation is defined in the same proximity, it's a contrary definition, plus the final formula surely can't be correct for the rising fact. notation, there must be a sign wrong. The casuaul reader could be easily mislead here. MaxEnt 09:52, 17 April 2006 (UTC)
I've seen other notation, specifically here [1], in the second question, and here [2] in questions 2iii and 2iv. Could someone who understands this a bit better than I do explain it, as it appears to be fairly common. 80.177.1.238 16:43, 8 March 2006 (UTC)
The section does not explain the notation for the identity perm in cyclic form. If all fixed points are omitted, one is lead to the conclusion that the notation for an identity perm. is an empty string. It also fails to point out an ambiguity where the last element is a fixed point (or tail suffix of such). You can't inspect cyclic notation with fixed points omitted to determine the number of elements in the perm. described, whereas without the omission of fixed points, the notation was entirely clear in both regards. MaxEnt 10:07, 17 April 2006 (UTC)
The "Abstract algebra" paragraph now seems obsolete and could be deleted, am I wrong ?
BTW, there's nothing wrong in defining a permutation of {1...n} once as a bijection from this set into itself, and once as a family (x1,x2,...,xn) of numbers from this set, each occuring once, since the two definition coincide (at least if we agree that such a family is indexed by {1,...,n}).
On the other hand there seems many many articles about the same subject, I try to start a non-exhaustive list:
I think they should be merged (urgently) or identified clearly (in each of the other articles) as the article treating a particular aspect of the thing (which should then not be discussed in any of the others). — MFH: Talk 22:53, 16 October 2006 (UTC)
And perhaps the solution method should be somewhere in the article. For example: The set {1, 2, 3, 4, 5, 6} has 720 different rearrangements (permutations of which n=6 and r=6). If the permutations were all put into matrices (in other words, if they were all in the matrix-esque display in the article), how many of them would apply to the following rules?: "s(x)=1, s(y)=2, s(z)=3, x<y<z" In other words, how many of these permutations would have the numbers 1, 2, and 3 in that order, including ones such as {6, 1, 2, 4, 3, 5} and {4, 1, 5, 2, 6, 3}? -Mr. Random
The algorithm presented in the article doesn't work with set equal or less than 2. Explication are missing about it.
in how many ways can the result of twelve soccer matches be arranged with either a win , draw or loss 41.210.20.124 ( talk) 18:12, 1 April 2009 (UTC)
The derivative page has five calculators in the external links and is rated higher than this page. Seems that makes for a better page. This is just not paper put to a Web page.
Warren Van Wyck ( talk) 01:40, 21 October 2009 (UTC)
I arrived planning to make the intro more layman-accessible, but now I'm confused myself. (Combinatoric) permutations can't use all the elements of the set? That's what I'm getting from "In combinatorics, the term permutation has a traditional meaning, which is used to include ordered lists without repetition, but not exhaustive (so of less than maximum length).". What would the, er, thingies 1,2,3, 2,1,3, and 3,2,1, taken from the set (1,2,3) be called, then? BTW, I'm a big proponent of putting a clear, simple example of a common case right up front so as to draw in the non-math types; I'll try to find a correct one once I figure out what's going on myself... Lunkwill 29 June 2005 07:38 (UTC)
The introduction is too long (WP:Lead). The historical information and quotation are obviously out of place. The remaining text should be trimmed down if possible. —Preceding unsigned comment added by NOrbeck ( talk • contribs) 20:35, 19 August 2010 (UTC)
In algebra and particularly in group theory, a permutation of a set S is defined as a bijection from S to itself (i.e., a map S → S for which every element of S occurs exactly once as image value). To such a map f is associated the rearrangement of S in which each element s takes the place of its image f(s). In combinatorics, a permutation of a finite set S is defined as an ordering of its elements into a list. In this sense, the permutations of S differ precisely by a rearrangement of their elements. For a set S that is given with an initial ordering, such as S={1,2,3,...,n}, these two meanings can be almost identified: applying a permutation in the first sense to this initial ordering gives an alternative ordering of the elements, which is a permutation in the second sense.
The term permutation is also used less formally to designate the act of rearranging parts of an object, or the result thereof. Thus one might define an anagram of a word as a permutation of its letters, or say that X3Y+7+Y2Z is (obtained by) a permutation of the terms of the polynomial X3Y+Y2Z+7. The act of permuting can also refer to substitution of symbols, for instance when saying that Y3Z+Z2X+7 is obtained from X3Y+Y2Z+7 by a (cyclic) permutation of the variables X, Y, Z. These statements can be given a precise meaning by considering an appropriate symmetric group action.
In combinatorics the second sense of "permutation" is sometimes broadened. In elementary combinatorics, the name " permutations and combinations" refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for k-permutations the order of selection is taken into account, but for k- combinations it is ignored. In fact counting k-permutations is used as a step towards counting the number of k-combinations, and also towards computing the number n! of permutations of the set (in either of the two meanings mentioned above). However k-permutations do not correspond to such permutations unless k = n, that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S, with a finite multiset M in which some values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M. Thus for M=[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M, but [3,1,2,1,2,3,1] is not.
Permutations occur, in more or less prominent ways, in almost any domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science. In algebra, an entire subject is dedicated to the detailed study of permutations, through the notion of symmetric group. The key to its structure is the possibility to compose permutations: by performing two given rearrangements in succession, the combination defines a third rearrangement.
The rule to determine the number of permutations of n objects was known in Hindu culture at least as early as around 1150: the Lilavati by the Indian mathematician Bhaskara II contains a passage that translates to
The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures. [1]
A first case where at first sight unrelated mathematical questions are studied with the help of permutations occurs around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. The development that came forth from this work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics there are many similar situations, where understanding a problem requires studying certain permutations related to it.
References
I have a feeling that there might be some statistical tests (say, nonparametric, just using ranks) that use facts from permutation.
A question, for example: If I draw from two distributions and order them in a single list, what is the probability that the observed permutation is at random (versus sufficiently disordered)? I know a Wilcoxon rank-sum test is a paired version. What about unpaired?
My point is it would be nice to work these references into the permutations article, or at least provide a cross-ref.
dfrankow ( talk) 21:16, 30 April 2009 (UTC)
Can you guys make thins simple to understand. Wiki pages on some topics are too obscure to understand. —Preceding unsigned comment added by 180.149.49.125 ( talk) 17:34, 19 March 2011 (UTC)
Could someone please re-mention the symmetry between decoding unique factoradic integer k for Permutations (Variable Bit Decoding) and Combinations (Constant Bit Decoding) since ite got nuked. Michael.Pohoreski ( talk) 17:02, 22 October 2010 (UTC) e.g. * http://en.wikipedia.org/?title=Permutation&oldid=342103380#Encoding_and_decoding
my calculator has a nPr button is this a common notation for purmutations? — Preceding unsigned comment added by 136.159.16.7 ( talk) 17:14, 22 September 2011 (UTC)
The lead section states in part:
Although this is mathematically correct, neither this nor the rest of the article make it clear to me for which n a permutation of a set of n objects is defined. I do not see any restriction on n in the article. I do not see n defined to be an integer, a natural number, etc. Specifically, does it make sense to speak of a permutation of an empty set? Would an expert on the subject of permutations please clarify these issues in the article? Thank you! — Anita5192 ( talk) 02:50, 28 February 2012 (UTC)
The illustration with the balls is kind of confusing. They should be separated so that the reader can see that the six sets are independent and not part of some sort of matrix of balls. — Preceding unsigned comment added by 71.239.6.227 ( talk) 02:58, 14 March 2012 (UTC)
Permutations is linked from cryptography pages, but it is not clear which definition applies. It would be nice if there was a more explicitate explanation of what a "permutation" is in the context of cryptography. 23.25.179.162 ( talk) 16:03, 3 October 2012 (UTC)
I have done extensive research on permutation and combination and found consistent result in my research. this result I have found is written in a book known as junction. To see my research result then log in to my sight https://sites.google.com/site/junctionslpresentation/home or e-mail me at Softlaws4095@gmail.com — Preceding unsigned comment added by 14.97.116.20 ( talk) 18:34, 24 April 2012 (UTC)
Now I have attached some microsoft word documents which gives some of the proofs of junctions on which I have done research. Please accept my research work this will enable for the convinient study of combination and permutation.
https://sites.google.com/site/junctionslpresentation/ — Preceding unsigned comment added by 27.5.177.192 ( talk) 14:50, 20 May 2012 (UTC)
The one in the article is by far the shortest I've come across. I've checked its outcome for various sequence lengths n, getting n! different arrangements each time, so conclude that it's valid. It would be nice if there was some explanation of the principle and a reference to its source. 86.132.234.4 13:31, 18 January 2007 (UTC)
It wasn't clear to me initially that the sequence index is 1-based, although looking at it now, the mathematical notation for the sequence does specify. Maybe this could be made clearer in the text? -- Lumimies 21:53, 1 May 2007 (UTC)
Yep pretty nice algo, many thanks for that. Using the factoradic on the fly is very good, I just pre-computed the factorial (from 1 to n) outside of the function to avoid recomputing at each call and zooooom...
I really think the algorithm should be changed to 0-based. Throughout other articles with array-processing algorithms, such as the Fisher–Yates shuffle, implementations are zero based. Zero-based arrays seem to very common in the field of computer science, and the algorithm should reflect that. I have attempted to change it on my own, but I have run into several bugs, especially when the length of the array given is 2. I think everyone would appreciate it if the algorithm was modified. Jessemv ( talk) 05:37, 20 November 2009 (UTC)
I was able to convert this algorithm to zero-based as follows: Have k run from 1 to n! inclusive. Then change the swap index calculation to s[k mod (j+1)], and have j run from 1 to (length(s)-1). The other swap index remains s[j] and the k update formula remains k/j (integer division with decimal truncation). Note you don't get the same permutations for the same values of k, nor is the order of permutations the same between these two versions. Let me know if you find an error or have a better zero-based index version. I don't have any bugs for s lengths of one or two with either version though. When I initially implemented this algorithm in C I made the mistake of not giving the algorithm the original s string for each value of k, so watch out for that. If you need an iterative permutation algorithm that gives the output in lexicographic order you can find one in the text Discrete Mathematics By Richard Johnsonbaugh. He also has source code posted here: http://condor.depaul.edu/~rjohnson/source/perm.c Qatux ( talk) 18:45, 20 November 2009 (UTC)
I tried using the algorithm to generate lexicographic permutations as described in this section. I was confused by the statement Since k + 1 is such an index, l is well defined and satisfies k < l in step 2 of the algorithm. It is true that l = k + 1 on the first permutation, but after the first permutation l can be equivalent to k + 2 or k + 3 ... etc. I thought having such a statement that is not applicable to all cases of permutation in the description of the actual algorithm was unnecessary and confusing. I added a walk through example of the algorithm in action as a contribution.-- James Lingford ( talk) 09:46, 7 August 2013 (UTC)
I recently converted the descriptor "sequence" for permutations to "ordered arrangement". This was reverted and I just re-reverted. My reasons for doing this are twofold. First, as I mentioned in my original edit, the term "sequence" is not quite correct, the proper term would be "sequence without repetition". If one were required to use this entire phrase, the appeal of this descriptor would soon vanish. One could say, early in the article, that for this article "sequence shall mean sequence without repetition", but this is a long article and readers do not always start at the top and read everything, so may fail to see that disclaimer. A further problem arises (and this is problem was never addressed) when permutations are applied to actual sequences and the term "sequence" had two meanings within the same sentence. Secondly, the term "sequence" is never used, outside of WP and its derivatives, except by a small cadre of computer scientists. The vastly predominant term is "ordered arrangement" and this can be found in high school texts, combinatorics texts and other elementary mathematics texts. By WP:Commonname this should be the term used in the article. We may or may not like the choice, but that is not our call to make. Note that in the later sections that deal exclusively with the computer science aspects of the topic, I left the sequence terminology in place with only a brief transitional comment about it. Bill Cherowitzo ( talk) 15:45, 9 June 2014 (UTC)
Article doesn't contain formula for case of permutations with repeated elements. http://www.vitutor.com/statistics/combinatorics/permutations_repetition.html
In some sources it denoted as variations with repetitions but Wikipedia seems to equate terms "variation" and "permutation". http://www.emathematics.net/combinavrepeticion.php LiberalDemocrat ( talk) 12:22, 28 December 2014 (UTC)
LiberalDemocrat ( talk) 10:53, 29 December 2014 (UTC)
Since participating at some length in this discussion four years ago, I've realized there is an even more fundamental problem here. The very first sentence of the article is as follows:
In mathematics, the notion of permutation relates to the act of rearranging, or permuting, all the members of a set into some sequence or order (...).
For a reader who knows the definition of set, this should fail to make sense. For a set has no initial order. A set is intrinsically unordered. How then can it be rearranged? It cannot be rearranged or, in common parlance, "permuted."
If for example you try to rearrange the set {pig, horse, duck} into, say, {horse, duck, pig}, you have merely shown an equivalent representation. Given that the notation {...} denotes a set, I insist without qualification that {horse, duck, pig} = {pig, horse,duck}.
If I must arrange the elements of a set, I am evidently forced to replace the set with an ordered tuple incorporating the same elements as the set. Thus the set {pig, horse, duck} must be replaced with a 3-tuple such as (pig, horse, duck), or (horse, duck, pig) before it can undergo a reordering operation. And as one more stroke of personal confusion, I find that I do not see how to specify a mapping between an arbitrary finite set and a tuple with the same number of elements as the set. For any specific set I can readily indicate such a mapping, but without having the elements of the set specified in advance, I am at a loss. Dratman ( talk) 00:26, 22 June 2015 (UTC)
Very good article. Very helpful. I commend you. — Preceding unsigned comment added by W1k13rh3nry ( talk • contribs) 23:58, 9 March 2007 (UTC)
— Preceding unsigned comment added by 201.255.142.74 ( talk) 22:23, 15 July 2009 (UTC)
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)
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)
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 Sadasivam
t@lk
05:55, 6 April 2016 (UTC)
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)
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)
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)
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)
In[1]:= Permute[(e,b,d,c,a),{3,5,1,2,4}] Out[1]= (d, a, e, b, c)
1 2 3 4 5 | | | | | 3 5 1 2 4
5 2 4 3 1 | | | | | 4 5 2 1 3
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 ... 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)
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)
Here is another typical instance of the problem, from Mathworld:
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)
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)
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)
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)