#include <iostream>
#include <vector>
#include <random>
#include <ctime>

// Function to perform Fisher-Yates Shuffle in place
void fisherYatesShuffle(std::vector<int>& arr) {
    // Initialize random number generator
    std::mt19937 rng(static_cast<long unsigned int>(time(0))); // Random seed based on time
    
    // Loop through the array from last element to the second element
    for (int i = arr.size() - 1; i > 0; --i) {
        // Generate a random index between 0 and i
        std::uniform_int_distribution<int> dist(0, i);
        int j = dist(rng);
        
        // Swap the elements at index i and index j
        std::swap(arr[i], arr[j]);
    }
}

int main() {
    // Create a vector (array) of song IDs
    std::vector<int> arr = {10, 20, 30, 40, 50};
    
    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";
    
    // Shuffle the array using Fisher-Yates
    fisherYatesShuffle(arr);
    
    std::cout << "Shuffled Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}