Talk:Permutation

Edit request

After being informed by MrOllie about a potential conflict of interest, I am now formally requesting to make the following additions to the page. The Combinatorial Object Server is a collection of open source software tools I frequently use to create this kind of illustrations, and to which I am a frequent contributor.

Extended content

A: Add the following paragraph to the Subsection "Generation with minimal changes": The following figure shows the output of all three aforementioned algorithms for generating all permutations of length $n=4$, and of six additional algorithms described in the literature. Ordering of all permutations of length $n=4$ generated by different algorithms. The permutations are color-coded, where 1=red, 2=yellow, 3=green, 4=blue. 1: Lexicographic ordering; 2: Steinhaus-Johnson-Trotter algorithm; 3: Heap's algorithm; 4: Ehrlich's star-transposition algorithm (see ): in each step, the first entry of the permutation is exchanged with a later entry; 5: Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation; 6: Sawada-Williams' algorithm: 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: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position; 8: Single-track ordering: each column is a cyclic shift of the other columns; 9: Single-track Gray code: 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: Permutation generation algorithms on the Combinatorial Object Server References

Torsten Mütze (talk) 19:07, 29 May 2019 (UTC)

Per my concerns at the bottom of Talk:Gray code (Special:PermanentLink/899583820#tbf-objection-2019), I object to the addition of the external link (B). I have no opinion on part A. ~ ToBeFree (talk) 23:45, 30 May 2019 (UTC)

• If this edit is done, I would change "Steinhaus-Johnson-Trotter" to "Steinhaus–Johnson–Trotter" (with an en-dash rather than a hyphen), per WP:MOS, and where it says "red=1" I would instead write "red = 1" (and similarly with the other colors, of course), since that is the standard format.

Contrast:

Steinhaus-Johnson-Trotter

Steinhaus–Johnson–Trotter

red=1

red = 1

Michael Hardy (talk) 21:16, 31 May 2019 (UTC)

 Done All proposed edits and suggested modifications for (A) have been implemented. The proposed additional links to the EL section (B) were declined. Thank you to everyone for their input. Regards,  Spintendo  15:59, 9 June 2019 (UTC)

Permutations with repetitions

In permutations with repetitions it has to be stated at least Tuple#n-tuples_of_m-sets as the word tuples alone is only the plural of tuple (ordered set or list) so ordered sets or lists and permutations without repetitions refers to a scalar number

It has to be clarified Tuples at least as Tuple#n-tuples_of_m-sets as Tuples alone is only the plural of Tuple and Permutations without repetition is a scalar number. Orendona (talk) 20:42, 1 November 2020 (UTC)

I see from your edits that you want to refer to the cardinality of the set of permutations with (or without) repetition. Is this the scalar number you mention above? This would be a very tortured way to approach the topic and demonstrates some deep confusion. --Bill Cherowitzo (talk) 21:56, 1 November 2020 (UTC)

That is the use, they are not tuples, they are a special kind of tuples: All the possible tuples that can be made with repeated or not members of a second set. And they are not permutations. Some of the tuples are permutations of others. Orendona (talk) 13:16, 3 November 2020 (UTC)

Add real notations in notation subtopic

Adding real notations in notation subtopic will help people new to this and it makes article more easy to read. Anish59312 (talk) 04:59, 13 July 2021 (UTC)

Confusing address and value

In the examples, slot numbers and values both use numbers, hiding the fact that the two are not the same. I propose that slots be identified by numbers, while values are letters. Comfr (talk) 16:50, 16 August 2021 (UTC)

Active and passive confusion in lede

When the lede moves from the intuitive notion of permutation as a rearrangement to the technical definition as a bijection, I'm afraid it just gives the passive "permutation", instead of properly constructing the function f that would actively perform the rearrangement, i.e. by moving the element i to the place f(i).

Specifically, the informal "permutation" which is the arrangement (3, 1, 2) of the numbers {1, 2, 3} should correspond to the function $\alpha$ accomplishing this arrangement by putting element i into place $\alpha (i)$, which implies $\alpha (1)=2,\alpha (2)=3,$ and $\alpha (3)=1$. The permutation presently given is actually the inverse, $\alpha ^{-1}$.

The preceding statement "This is related to the rearrangement..." suffers from the same confusion, on top of mistakenly "rearranging" an arbitrary (unordered) set S. I suggest that this sentence should be removed while a similar, corrected, explanation is adapted to the specific example and inserted into the following sentence. ––St.nerol (talk) 21:16, 16 September 2021 (UTC)

There is no correction to be made here. There are two reasonable conventions for how to record a bijection from {1, ..., n} to itself as a sequence. I believe that the article is internally consistent in choosing the convention that the sequence corresponding to the bijection a is $(a(1),\ldots ,a(n))$ (the one-line notation). In my experience, this is also the convention overwhelmingly used by combinatorialists. It happens that you are using the other convention. --JBL (talk) 20:32, 17 September 2021 (UTC)

@JayBeeEll: Not so fast! I'm aware of the ambiguity and I'm not really taking sides. (I agree we should use what's most common.) Carefully re-reading, I can very explicitly show how the lede is not consistent with the body, with the lede seemingly following an older convention. Please, hear me out.

The Definition-section points out that the modern view is "a permutation is a function that performs the rearrangement [while] an older and more elementary viewpoint is that permutations are the rearrangements themselves. To distinguish between these two, the identifiers active and passive are sometimes prefixed." It is perhaps not entirely clear how "active" and "passive" are used here, but Wikiversity gives an explanation which is at least related: "an active permutation $\pi$ [...] moves an object from place $i$ to place $\pi (i)$". Now, this is the exact opposite of what's described in the lede, in which "each element s is replaced by the corresponding f(s)". This is, instead, what Wikiversity describes as the passive convention.

Now, the active permutation, as defined above, is clearly used in the section "Matrix representation". Consider the permutation $\pi$, which can be read from the matrix according to the instructions σ(j) = i if M_i,j = 1. This gives $\pi (1)=3$, $\pi (2)=1$, $\pi (3)=2$, in one-line notation 3 1 2, and still, explicitly, $\pi (1,2,3)=(2,3,1)$. So $\pi$ is the permutation 3 1 2, which rearranges (1,2,3) into (2,3,1). This is just fine, provided the one-line notation is just a compact way of writing down the bijection as an active permutation.

The two math books I've consulted are not so concerned about the interpretation as a rearrangement and just mention it in passing. But of course, it's sensible that Wikipedia starts out by introducing the arrangement (3,2,1) as a "permutation", before segueing over into the formal treatment. However in order to have the arrangement (3,2,1) simply correspond to the one-line permutation 3 2 1, I'm afraid we'd actually have to use the older, passive convention – throughout! (And I'm not suggesting that.)

If you're not fully convinced, I'd at least ask for a clarify-tag at the sentence which begins "This is related to" and a dubious–discuss-tag at the following "For example". – St.nerol (talk) 19:04, 27 September 2021 (UTC)

It seems to me that your quibble is with Wikiversity, not with Wikipedia. From a group-theoretic perspective, the symmetric group $S_{n}$ can act on words from both the left and the right; one of these actions permutes "by value", the other one permutes "by position". As long as you believe the group is a separate object from the words, you are taking the "active" perspective. By contrast, the passive perspective is that permutations are the lists (with no group structure). It is unfortunate that combinatorialists have not adopted a uniform "right-hand rule"-type approach that resolves, arbitrarily but unambiguously, the inherent notational ambiguities around these questions; nevertheless, the convention followed in the lead of this article is consistent with the convention followed in the body, and that's what matters. --JBL (talk) 20:16, 27 September 2021 (UTC)

@JayBeeEll: The convention used in the section "Matrix representation" in this article is inconsistent with the lede. –St.nerol (talk) 21:08, 27 September 2021 (UTC)

It seems, actually, that it is the instruction for reading the matrices that is wrong. The given (σ(j) = i if M_i,j = 1) is the row representation; the matrices (for $\sigma$ it doesn't matter) are written in the column representation. This made me mistake the notation $\pi (1,2,3)=(2,3,1)$ to mean the permutation $\pi$ acting upon $(1,2,3)$; it seems to mean just $(\pi (1),\pi (2),\pi (3))$. –St.nerol (talk) 21:32, 27 September 2021 (UTC)

I wrote the following thing while you were revising; I leave it here so I don't lose it, and will seek to address your new comment shortly:
At first glance, I don't think you are correct -- in that section, $\pi (1,2,3)=(2,3,1)$ means that pi is the function such that pi(1) = 2, etc., just as in the introduction. (The second sentence of the section does seem dubious to me -- surely the convention being described involves multiplying the permutations in the opposite order of the matrices? -- but my impression is that's not your issue with it.) --JBL (talk) 21:52, 27 September 2021 (UTC)

Well, that section is rather weird, isn't it? The first paragraph says "you should do it in way X to get effect Y", but then the example does it in way not-X and we get not-Y (namely, the permutations and matrices multiply in the opposite order). ¯\_(ツ)_/¯ (But there's still no problem in the lead.) --JBL (talk) 21:58, 27 September 2021 (UTC)

...and all of a sudden a side point has become the main point! Right, and there seems to be more than one problem in that section. Please check again the matrix that's supposed to represent pi. Since 2 = pi(1) we should have M_{2,1} = 1. But instead we're given M_{1,2} = 1. –St.nerol (talk) 22:19, 27 September 2021 (UTC)

Looking again, I'm not convinced that there is a "not-X not-Y"-problem. –St.nerol (talk) 22:24, 27 September 2021 (UTC)

The first paragraph says, correctly, that if you define a matrix P_{pi} via P_{i, j} = 1 if i = pi(j) and all other entries are 0, then P_{pi} * P_{sigma} = P_{pi * sigma}. The third and fourth paragraphs use the opposite convention: they associate to each permutation pi the matrix (P_{pi})^(-1), correctly observe that with this (inverse) convention matrices and permutations multiply on opposite sides, and then do an example using this inverse convention (with the same one-line representation of permutations as in the lead section). There are no substantive errors here, but there is an unforgivable re-use of the notation M_pi to mean two inverse things, and no clear indication to the reader that two (incompatible) conventions are being used in close quarters. I haven't looked at the images (linked or displayed) to see how they fit in. --JBL (talk) 01:43, 28 September 2021 (UTC)

I now agree that your analysis of this problem is correct. –St.nerol (talk) 10:55, 28 September 2021 (UTC)

I have attempted to rewrite the section on matrices to be less confusing. (Even better would be to find some references, which I have not done.) --JBL (talk) 14:17, 28 September 2021 (UTC)

Mentioning that disjoint cycles commute in Cycle Notation section

The Cycle Notation section explains that many different cycle notations are possible for the same permutation because the starting point for each cycle can be any element in the cycle and then it goes on to give examples; however, the first example given, (125)(34)=(34)(125), is of two equivalent cycles whose order is commuted but whose starting points are unchanged.

This is doubly confusing because the article clearly states that permutations do not in general commute but does not mention that an exception to this general rule is when the permutations are disjoint.

My suggestion is either to move the (125)(34)=(34)(125) example to its own separate paragraph which explains that disjoint permutations commute and hence give rise to multiple cycle notations for the same permutation or to reword the current paragraph in line with my edit at 19:07, 21 January 2022. Obtuse Wombat (talk) 19:23, 23 January 2022 (UTC)

The fact that disjoint cycles commute is important in its own right, separate from the fact that many cycle notations are possible. Its omission was a deficiency in the section, but it did not belong in the sentence where you stuck it. I have done a thing, hopefully it is agreeable. --JBL (talk) 19:50, 23 January 2022 (UTC)

Separately, "rational" is an adjective, the noun you wanted is "rationale". --JBL (talk) 19:51, 23 January 2022 (UTC)

Thanks JBL, your change is much better. And also thanks for the pointer to WP:BRD. Incidentally, I did think I was following a standard process based on the second sentence of the "Discuss edits" paragraph of How to use article talk pages, which I was led to via a Google search on "how to dispute reverts on a Wikipedia article". Obtuse Wombat (talk) 21:08, 23 January 2022 (UTC)

@Obtuse Wombat: My edit summary was a snarky reaction, before I had taken the time to think about the content of your post here. I should have read and reflected for a moment first, before re-reverting and snapping. Sorry about that. --JBL (talk) 13:56, 26 January 2022 (UTC)

A nasty organization problem we need to fix

Here is the problem:

1. Permutation#Permutations_without_repetitions contains the sentence: "In a similar manner, the number of arrangements of r items from n objects is considered a partial permutation. It is written as $nPr$ (which reads "n permute r"), and is equal to the number $n(n-1)\cdots (n-r+1)$ (also written as $n!/(n-r)!$)"
2. Permutation#k-permutations_of_n restates the same information, but with more detail: "A weaker meaning of the term permutation, sometimes used in elementary combinatorics texts, designates those ordered arrangements in which no element occurs more than once, but without the requirement of using all the elements from a given set...(discussion w/ link to Partial permutation#Restricted partial permutations) ..."$P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }$"
3. Partial permutation#Restricted partial permutations complicates matters even more by stating: "Some authors restrict partial permutations so that either the domain or the range of the bijection is forced to consist of the first k items in the set of n items being permuted, for some k. In the former case, a partial permutation of length k from an n-set is just a sequence of k terms from the n-set without repetition. (In elementary combinatorics, these objects are sometimes confusingly called "k-permutations" of the n-set.)" TO MAKE MATTERS WORSE, THIS LINK TO THE PAGE k-permutation is a redirect to this article's Permutation#k-permutations_of_n

I hesitate to fix this problem myself, but my tentative plan is to delete the last sentence in Permutation#Permutations_without_repetitions, i.e., the one that begins,

"In a similar manner ... $n(n-1)\cdots (n-r+1)$ (also written as $n!/(n-r)!$)

Then I will go back to Partial permutation#Restricted partial permutations, and rewrite the sentence with the words "confusingly called".

Yours truly, Guy vandegrift (talk) 03:38, 24 January 2022 (UTC)

@Guy vandegrift: Can you identify precisely what you think the nature of the problem here is? (It's not clear to me from the juxtaposed quotes + suggested edits.) The words "permutation" and "partial permutation" are used for several different but closely related concepts, so there's bound to be some overlap and there's also bound to be some inconsistency (because sources are not consistent in how they use these terms). Quite possibly our articles on these topics could be clearer about both the overlap and inconsistency, but I'm not sure how your proposed deletions help with that. --JBL (talk) 14:03, 26 January 2022 (UTC)

@JayBeeEll: At the very least, we need to fix the fact that $n!/(n-r)!$ is introduced twice in the same article. Let me explain why this is confusing: It is common to skim an article before deciding whether to carefully read it. A superficial explanation at Permutation#Permutations_without_repetitions, followed by a more complete explanation at Permutation#k-permutations_of_n renders this difficult.

I appreciate your hesitancy to delete the first mention of this formula, since there is a reason to bring this up early in the article. A perfectly acceptable solution would be add a sentence linking the first mention to the second. And, since such an edit is so easily reverted, I will perform that myself. After that, I just need to clean up the redirect at the other article. Guy vandegrift (talk) 17:54, 26 January 2022 (UTC)

"cycle type" vs "cycle structure"

Which term should be used to describe the type of a permutation in this article: "cycle type" or "cycle structure"? Both are common but Google gave 23,900 hits on my search for 'permutation "cycle type"' and 32,900 hits for 'permutation "cycle structure"', so on 6 August 2022 I edited the article to consistently use "cycle structure" (but mentioned that "cycle type" was also used). This edit was reverted, so I posted this talk page section to discuss the issue. Prior, to my earlier 30 July 2022 edit, this page confusingly used four terms to refer to the same thing ("cycle type" 3 times, "cycle structure" 1 time, "permutation type" 1 times, and "type" (by itself) 2 times). Based on the Google stats, I think it would be best to use "cycle structure" and mention "cycle type" as an alternative term. Even if we stick with the reversion to "cycle type", "cycle structure" should be mentioned as an alternative term. Obtuse Wombat (talk) 19:06, 7 August 2022 (UTC)

Thank you for cleaning up the article; I agree that the prior state was confusing.
The search you describe does not answer the relevant question, because it doesn't indicate how the terms are being used. Personally, I would use both phrases, but with slightly different meanings: I think it is common to use the words "cycle structure" when speaking loosely but I think it is rare to write a formal definition of "cycle structure". So I would expect that most uses of "cycle structure" could be replaced with "cycle type" with no loss in meaning, but that the reverse is not necessarily true. (Obviously I am relying heavily on vibes here.) --JBL (talk) 20:07, 7 August 2022 (UTC)

Example image should consider various visual disabilities

People who have visual disabilities -- most notably color blindness -- can have problems with the Permutations example graphic. Instead of having all circles/balls, why not have different shapes? Colors could still be used for clarity, but there are some common pairs of colors to try to avoid, like red-green or green-blue. Keeping a high contrast for those who have issues with contrast is also important. To help contrast, maybe highlight each shape with a white or black outline, etc. Or, just use black & white for the different symbols.

Any graphic should have proper ALT text explaining what is visually in the image, of course. ALT text would not explain the mathematical significance; that's left for the image caption. Wikispherion (talk) 16:52, 25 January 2023 (UTC)

Why the tilde in the notation for the definition of permutation?

Is this meant to indicate that σ is a bijective function? Klauscougar (talk) 21:26, 29 October 2023 (UTC)

Yes. --JBL (talk) 00:01, 30 October 2023 (UTC)