Shuffle the array variables in the given order without using the additional memory "input array size",

Question

Input:

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

Conclusion:

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

Condition: Do not use an additional array as memory. May use an additional variable or two.

Problem: I have the following C ++ program, but this fails for certain inputs of the 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

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

, P .
p = {1, 4, 3, 2, 0, 5}. : 0 => 1 => 4 => 0, 2 => 3 => 2 5 => 5. .

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

( , ). :

    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;
    }

, P "". , - , , .

Answer 2

, P, , , , :

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

P, ( , A ).

, , ; , .

Answer 3

int _tmain(int argc, _TCHAR* argv[])
{
    A[4] = {0,4,-1,1000}
    P[4] = {1,0,3,2}
    int temp = arr2[0];

    for(int i=0;i<4;i++)
    {
        for(temp = P[i];i<3;temp = P[temp])
        {
        if(temp >= i)
        {
            int data; 
            data = A[i];
            A[i] = A[temp];
            A[temp] = data;
            break;
        }
        }

    }
    _getch();
    return 1;
}

Answer 4

int _tmain(int argc, _TCHAR* argv[])
{
    A[4] = {0,4,-1,1000}
    P[4] = {1,0,3,2}
    int temp = arr2[0];

    for(int i=0;i<4;i++)
    {
        for(temp = P[i];i<3;temp = P[temp])
        {
        if(temp >= i)
        {
            int data; 
            data = A[i];
            A[i] = A[temp];
            A[temp] = data;
            break;
        }
        }

    }
    _getch();
    return 1;
}

Answer 5

dest

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 6

, , ( ) ( ). P , FWIW - ...

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;
    }
}