Why do we use the word "permutation" like this?

Правка en5, от InternetPerson10, 2023-06-05 00:54:02

There are many problem statements on Codeforces, especially in recent rounds, that use some variation on one of the following lines:

You are given a permutation of length n.

A permutation is an array of length n, consisting of each of the integers from 1 to n in some order.

If we take the dictionary definition of the word "permutation", this doesn't make sense. Strictly speaking, a permutation refers to an arrangement of some objects. Using the term by itself is meaningless, unless we define some set whose elements we can permute.

I'm not saying that we shouldn't be using the word "permutation" in this context. In fact, each of the following would be a semantically valid way to describe such a situation:

  • You are given a permutation of the integers from $$$1$$$ to $$$n$$$.
  • At least how many operations should be performed until the array becomes a permutation of $$$[1, 2, ..., n]$$$?
  • You are given an array of length $$$n$$$, consisting of each of the integers from $$$1$$$ to $$$n$$$ in some order.

The last one doesn't even require the use of the word "permutation"! If we only need to define such an array once, that would be the best option. There's no need to define the term "permutation" anymore.

Even the following would be valid:

  • A permutation of $$$[1, 2, ..., n]$$$ is an array of length $$$n$$$, consisting of each of the integers from $$$1$$$ to $$$n$$$ in some order.

The important part is defining what we are permuting here, and in most problems on Codeforces, mentioning the integers from $$$1$$$ to $$$n$$$ suffices.

I am aware that in competitive programming problems, calling such arrays "permutations" would be understood by a large majority of the community. I'll admit that in my experience, this does make statements easier to understand and solution discussions flow faster, so long as everyone involved knows what it actually refers to. But that last clause is important, and may confuse someone who sees the term in this context for the first time. It definitely ticked me off the first time I saw it, and it irks me that people look at an array of integers and call it a "permutation" without context.

Since when was the term "permutation" used like this? Is this usage prevalent outside the competitive programming community?

Thank you so much for reading.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский InternetPerson10 2023-06-05 00:54:02 0 (published)
en4 Английский InternetPerson10 2023-06-05 00:51:35 18 less accusatory tone (saved to drafts)
en3 Английский InternetPerson10 2023-06-04 14:09:54 0 (published)
en2 Английский InternetPerson10 2023-06-04 14:09:27 102
en1 Английский InternetPerson10 2023-06-04 14:01:42 2353 Initial revision (saved to drafts)