Shuffle array variables in a pre-specified order, without using extra memory of "size of input array"

Question

Input :

  A[4] = {0,4,-1,1000} - Actual Array
  P[4] = {1,0,3,2} - Order to be reshuffled 

Output:

    A[4] = {4,0,1000,-1}

Condition : Don't use an additional array as memory. Can use an extra variable or two.

Problem : I have the below program in C++, but this fails for certain inputs of array P.

#include<iostream>

using namespace std;

void swap(int *a_r,int *r)
{
    int temp = *r;
    *r = *a_r;
    *a_r = temp;
}
int main()
{
    int A[4] = {0,4,-1,1000};
    int P[4] = {3,0,1,2};
    int value = A[0] , dest = P[0];

    for(int i=0; i<4;i++)
    {
        swap(&A[dest],&value);
        dest = P[dest];
    }
    for(int i=0;i<4;i++)
        cout<<A[i]<<" ";
}

Answer 1

Since you've got a spare array called P kicking around, and there isn't anything in the question as quoted that stipulates it must be treated as a constant array, you could do:

for (i = 0; i < 4; i++)
    P[i] = A[P[i]];
for (i = 0; i < 4; i++)
    A[i] = P[i];

If you're not allowed to modify P, then you have to work a lot harder (and you also have to work a lot harder if the data type of A is not the same as, or compatible with, the type of P).

However, I fear this is a sleight-of-hand trick that doesn't really answer the question; it gets the job done, but doesn't answer the question.

Answer 2

First of all, I really like Jonathan's solution, but I feel like I can add some interesting ideas too.

The main observation is that array P consists of several loops.
Let's consider p = {1, 4, 3, 2, 0, 5}. There're three loops: 0 => 1 => 4 => 0, 2 => 3 => 2 and 5 => 5. And to replace variables alongside one loop we need no additional memory at all. We just go through it like this

do {
    a[i] = a[p[i]];
    i = p[i];
} while (i != first_i);

(The last element needs to be taken special care of, though.) The full working version:

    for (int i = 0; i < n; ++i) {
        if (p[i] < 0) {
            // been at index 'i' already
            continue;
        }

        // new loop found
        int j = i;
        int first_value = a[i]; // to be put in last position in the chain
        int prev_j; // we always store previous 'j' index
        do {
            a[j] = a[p[j]];

            prev_j = j;
            j = p[j]; // move to next 'j'
            p[prev_j] = -1; // mark element as processed
        } while (i != j);
        a[prev_j] = first_value;
    }

The only problem with my solution is that it uses p array to mark element as 'processed'. Some interviewers may consider it ok, others - not, depending on the solution they have in mind.

Answer 3

Slightly modified to calculate dest value

int main()
{
    int A[4] = {0,4,-1,1000};
    int P[4] = {3,0,1,2};
    int value = A[0], dest = P[0];

    for(int i=0; i<4-1;i++)
    {
      int count=0;
      dest = P[i];
      while(dest<i){ //if P[i] points to lower value, it got swapped with some other position. 
        dest = P[dest];
      }
      swap(&A[dest],&A[i]);
    }
    for(int i=0;i<4;i++)
        cout<<A[i]<<" ";
    cout<<"\n";
}       

Answer 4

Could argue that it goes against the spirit of the question - but can use multiple stack instances (from a run-time perspective) of a single local variable (code perspective). Being allowed to mutate P is just as uncertain, so, FWIW - a recursive answer...

template <int N>
void shuffle(int (&a)[N], int p[], int i = -1)
{
    if (++i < N)
    {
        int result = a[p[i]];
        shuffle(a, p, i);
        a[i] = result;
    }
}