Shuffle Array - C++ Solution

1. Introduction

In this blog post, we'll address a practical problem in array manipulation: in-place shuffling an array based on an order specified by another array. This problem is an interesting application of array indexing and element swapping in C++.

Problem

Given two arrays, nums (containing distinct integers) and pos (specifying an order), the task is to shuffle nums in-place so that each element nums[i] is moved to nums[pos[i]].

Example:

Input: nums[] = [1, 2, 3, 4, 5], pos[] = [3, 2, 4, 1, 0]

Output: [5, 4, 2, 1, 3]

2. Solution Steps

1. Iterate through the nums array.

2. For each index, swap elements until the current element is placed in its correct position according to pos.

3. Handle the case where an element needs to be placed in its current position.

4. Continue this process for each element in nums.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to in-place shuffle the array
void shuffleArray(vector<int>& nums, vector<int>& pos) {
    for (int i = 0; i < nums.size(); ++i) {
        while (pos[i] != i) {
            swap(nums[i], nums[pos[i]]);
            swap(pos[i], pos[pos[i]]);
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    vector<int> pos = {3, 2, 4, 1, 0};
    shuffleArray(nums, pos);

    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Output:

5 4 2 1 3

Explanation:

The shuffleArray function iterates through the nums array. For each index i, it performs swaps to place the element nums[i] at the position nums[pos[i]], also updating pos to reflect the change. The swapping ensures each element is moved to its correct position according to pos. This in-place shuffling is demonstrated in the output for the given example.