The permutation problem. C++
For a given permutation, you need to determine the inverse.
A permutation of N elements is an ordered set of N distinct numbers from 1 to N. The number of different permutations of order N is PN = N!
Let us have an ordered set of N elements. The permutation specifies the transformation of this set. Namely, it says that in i place you need to put the ai element of the set, where ai - i-th element of the permutation.
The inverse permutation to the permutation π is called such a permutation π-1, that ππ-1 = π-1π = ε, where ε is the identity permutation. That is , if we first apply the permutation π, and then the inverse of it π-1, then in the end we get the result as if we did not apply these permutations at all. The same result is obtained if we first apply the inverse permutation π-1, and then the direct π.
Input data In the first line input file INPUT.TXT the number 0
Output data To the output file OUTPUT.TXT output the reverse permutation.
I will briefly explain what they want from us.
[5,7,4] - массив
(2,1,3) - перестановка
[7,5,4] - результат
(2,1,3) - обратная перестановка (обратная перестановка не всегда равна перестановке)
[5,7,4] - результат. (мы вернулись к исходному массиву, что и нужно было)
Ответ: (2,1,3)
Let's say we have an array a - [5,7,4] and have its permutation (2,1,3). This means that I put the second element in the first cell of the array. That is, a[0] = 7. On the second - the first a[1] = 5. On the third - the third a[2] = 4. But we you also need to find the reverse permutation. So you need to find a permutation that will return to the original array.
The idea of my solution:
An array of numbers can be immediately represented as a sequence of natural numbers from 1 to n. That is, for example, the array I have is a permutation of (2, 3, 4, 1) and an array of [1,2,3,4]. The final result will be this permutation - [2,3,4,1]. So it is necessary to make an increasing permutation from the permutation (2,3,4,1) - (1,2,3,4), hence the idea of the solution.
Looking for minimum numbers in order and output their indexes (numbering from 1).
Solution code:
#include <bits/stdc++.h>
using namespace std;
bool used[20001]; //записываем минимумы которые уже использовались
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto& b : a)
cin >> b;
for (size_t i = 0; i < n; i++)
{
int min = 20001;
int mini = -1;
for (size_t j = 0; j < n; j++)
{
if (min > a[j] && !used[a[j]]) //поиск неиспользованного минимума
{
min = a[j];
mini = j;
}
}
used[min] = true; //использованный минимум больше не трогаем
cout << mini + 1 << " ";
}
}
On tests, he writes that my program has run out of time for tests. Although this is not surprising. The asymptotics of O (n^2) ~ 4*10^8 actions. In fact, I very much doubt about my implementation and I really think that everything can be implemented much easier here.
-
Even if the idea of my solution is wrong (in terms of efficiency), have I effectively implemented my own an idea?
-
Can you think of something better?
2 answers
Let's start with the fact that your program works very poorly, because 4*10^8 degrees is too much luxury, and in one second it is very unlikely to have time to work. And here everything is simple. In this problem, we need to make it so that when the reverse permutation occurs, the value returns to the initial one. To solve the problem, we need to understand that this operation is a transfer of a value from position i to position Mas[i]. This means that in the reverse permutation, the value from the position Mas[i] goes to i. That is,, for these values to be the same, we just need to have the value i in our response to the Mas[i] position. The implementation is very simple:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>Mas(n + 1);
vector<int>Res(n + 1);
for (int i = 1; i <= n; i++) {
cin >> Mas[i]; //считываем массив
}
for (int i = 1; i <= n; i++) {
Res[Mas[i] ] = i ; //Присваиваем каждому Mas[i] элементу значение i
}
for (int i = 1; i <= n; i++) {
cout << Res[i] << " ";
}
}
Yes, we do not need two arrays here... Just immediately collect the array for output, without saving the input.
#include <iostream>
int i,N,a,b[20002];
main()
{
std::cin>>N;
for(;std::cin>>a;b[N-a]=++i);
for(;N--;) std::cout << b[N] << " ";
}
If it is not very clear - well, so it is acmp, they want brevity... :)