In this article we are going to discuss an interview question that is asked quite frequently in companies like Facebook, Microsoft, or Google.
The problem statement goes as follows: Given an vector<T> A of elements of type T of length Nand a vector<size_t> P where Pis a permutation of numbers from [0-N-1]you need to apply the permutation Pto the vector A. You are not allowed to use more than O(1) additional space.
For example suppose A=['a','b','c','d'] and P=['2','0','4','1']. After applying P to A, the latter becomes: ['c','a','d','b']. P[i] basically tell you which element of A should go in position i in the final arrangement of A.
Solving this problem can be very easy if you are allowed to use additional O(n) memory. All you need to do is to construct a new array, taking the elements as specified in P. The following code shows how this approach can be implemented in C++
template<typename T>
void apply_permutation(vector<T>& A, const vector<int>& P)
{
vector<T> A1;
A1.reserve(A.size());
for(size_t i = 0 ; i < A.size() ; i++)
A1.push_back(std::move(A[P[i]]));
A = move(A1);
}
Note how we use move which will avoid the copy if possible) of potentially heavy objects. Once the additional array A1 has been constructed, we modify A by moving A1 into it. That is pretty easy stuff.
In order to solve the hardest version we need to work a bit more.
The approach that will lead to the correct solution goes as follows: for each element that it is not yet in the correct location, then move it to its correct location. Sounds easy, and in-fact it it. Let's use the following concrete problem instance example as a guide:
- A = [a,b,c,d,e,f]
- P = [3,1,0,2,5,4]
For i = 0 we notice that P[i] != 0, meaning that in A[i] we should moveA[3]. In order to achieve so we swap(A[i], A[3]) which results in A=[d, b, c, a, e, f]. Now the first position of the answer is correct. Well done.
But we moved element originally at positioni=0to position 3which is clearly not its correct position ( because according to P, a should be placed in position 2). What do we do? We swap the correct element ( A[P[3]]) with A[3]=a . In other words we substitute the awith the element that should really go in that position i.e. c. After swap(A[3], A[2]), A=[d,b,a,c,e,f]. a is now not at location 2 and P[2] says that the element that should go here is a. good, we found the correct spot for the element originally in position i=0. In the process we also placed many other elements in the correct position.
Ideally now we should process another element that is not in its correct location. But how do we know which one is in the correct location? Since we cannot use any additional memory, we need to be clever and use P instead. What if we set P[i] = iwhenever we do a swap? If we do that then we do not really do nothing for that element because when P[i]= ithere is no work to do, as the element is already in its final location.
If we apply this line of reasoning to all elements of A then the final result will be what we really expected. Basically for an element i not yet in its correct location we keep swapping it until it reaches its final location. If we do it for all elements, then by definition we have solved the problem.
I am sure the idea above will be much more clear once we look at the code: curr and next are respectively the indices of the elements we are considering for a swap.
template<typename T>
void apply_permutation_in_place(vector<T>& A, vector<int>& P)
{
for(size_t i = 0 ; i < A.size() ; i++){
size_t curr = i;
size_t next = P[curr];
while(next != i)
{
swap(A[curr], A[next]);
P[curr] = curr;
curr = next;
next = P[next];
}
P[curr] = curr;
}
}
You can try the above code online on wandbox ( https://wandbox.org/permlink/NevnhZFq2G0cgL7O ).