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.
Since when was the term "permutation" used like this?
This has been used for a long time. I don't know if using the word "permutation" to refer to a permutation of $$$1..n$$$ has increased recently, but there is this old problem from 7 years ago that does this:
612E - Корень квадратный из перестановки
From the statement
A permutation of length $$$n$$$ is an array containing each integer from $$$1$$$ to $$$n$$$ exactly once.
I personally don't like this as much. I think that the best and cleanest way to say this would be the first option you mentioned. If people don't know what "permutation" means in this context, they can look it up and understand that a permutation of the integers from $$$1$$$ to $$$n$$$ is some arrangement of these integers.
When I solve a problem that has an array I will usually read the statement to get an idea of the general problem I'm trying to solve, then I'll come back to answer several questions that come to my mind, such as "can the array contain repeated elements?" and "what is the range of the values in the array?". Saying permutation answers all such questions in a single word, it's very useful.
So I think "an array consisting of each of the integers from 1 to n in some order" is inferior to "a permutation" for a similar reason that I'd prefer statements use "you are given a tree" instead of "you are given a graph that is undirected, connected and has no cycles". I could live with "a permutation of the integers from 1 to n", but even that feels verbose for such a common object.
I personally don't get the same feeling with the use of tree, bec the use of the term "tree" as a connected undirected acyclic graph is unambiguous and known outside of CP, but the use of "permutation" as a list of integers from 1 to n isn't. Might just be a personal preference, then.
The term "permutation" in this case does help to grasp statements faster, and you explained it really well. Thanks :)
For Codeforces, I believe the main reason is simply that it is in the problemsetter's rulebook.
On a side note, I would argue that what is called a permutation here is actually not a permutation either, but a linear order, because permutation is actually a bijection from a set onto itself, while a linear order is an arrangement of the set elements in, well, some specific order, i. e. a bijection from $$$[1, 2, \dots, n]$$$ onto the set.
While the concepts are essentially the same when applied to $$$[1, 2, \dots, n]$$$, they're somewhat different in other contexts (e.g. permutations and linear orders considered to be distinct combinatorial species).
+1, it annoys me to no end that the first thing that people think of when they read the word permutation is an array of integers — I wrote a blog on permutations that hopefully makes it clear why it is much better to think of them in terms of shuffling things around.
While we're at it, the combinatorial species of linear orders and permutations are very different (and not isomorphic either) because these are very different things fundamentally.
because people prefer ease to being correct. i dont really see why people are obsessed over using the words only in the correct dictionary definition, especially when its even defined below differently.
I think initially this shortened version leaked into English as an inaccurate translation: in Russian, the direct translation of a permutation is widely understood as a permutation of integers 1 to n, especially in a math context. For example, the Wikipedia article for "permutation" in Russian gives this definition and only briefly mentions other objects.
Now the question is whether we should return to the full form (I will correct the guidebook then), or whether the short form is already accepted by the community, especially given the accompanying definition. What are the opinions here?
Apart from what permutation means or whatnot, I prefer this phrase, since it doesn't use new words and still being very concise:
"You are given an array of length $$$n$$$, consisting of each of the integers from 1 to $$$n$$$ in some order."
is it really concise compared to "You are given a permutation of size n"?
Generally, you can't say that in serious competition. You should at least state if it's $$$[0, n - 1]$$$ or $$$[1, n]$$$.
You are definitely right that we are not using it correctly. But this is for the sake of brevity. One word "permutation" conveys a lot of information that is much easier to quickly internalize than "array of length n of distinct integers from 1 to n". The cost of being not fully correct is negligible as this does not lead to any confusion, but even if somebody is somehow confused, input description or sample input will make it clear right away.
Thanks for the blog, I totally agree. Everyone please avoid "You are given a permutation of length $$$n$$$." in the problem statements.
I'd suggest "You are given a permutation of $$$(1,2,\ldots,n)$$$." (or $$$(0, 1, \ldots, n-1)$$$ or whatever) — This is correct, concise, and easily recognizable.
Exactly, when I encountered my first 'permutation' problem, I was so confused! I'm fine now of course, but I still feel like it should be used correctly.