|
Given two arrays arr[] and P[] of length N and an integer K. The task is to find the final array if permutation P[] is applied on given array arr[] for K times. If we apply a permutation P[] on array arr[] we get a new array arr’, such that arr'[i] = arr[P[i]].
Examples:
Input: N = 4, K = 2, P = {2, 3, 4, 1}, arr = {2, 1, 3, 4}
Output: 3 4 2 1
Explanation:
After applying permutation P to arr[] once,
arr’ = [1, 3, 4, 2]
arr'[1] = arr[P[1]] = arr[2] = 1
arr'[2] = arr[P[2]] = arr[3] = 3
arr'[3] = arr[P[3]] = arr[4] = 4
arr'[4] = arr[P[4]] = arr[1] = 2
After applying permutation P to arr[] twice,
arr” = [3, 4, 2, 1]
arr”[1] = arr'[P[1]] = arr'[2] = arr[P[2]] = arr[3] = 3
arr”[2] = arr'[P[2]] = arr'[3] = arr[P[3]] = arr[4] = 4
arr”[3] = arr'[P[3]] = arr'[4] = arr[P[4]] = arr[1] = 2
arr”[4] = arr'[P[4]] = arr'[1] = arr[P[1]] = arr[2] = 1
Input: N = 4, K=3, P = [2, 3, 4, 1], arr = [2, 1, 3, 4]
Output: 4 2 1 3
Explanation: After applying the permutation P to arr[] three times, we get arr”’ = [4, 2, 1, 3]
Approach:
The problem can be solved using Binary Exponentiation. If we observe carefully, we will notice that applying a permutation to arr[] two times is same as applying a permutation on itself and then applying it on the arr[]. Similarly, applying a permutation to arr[] 4 times is same as applying the permutation on itself for 2 times and then applying it on the arr[].
Therefore, we can say that applying a permutation to arr[] for 2^N times is same as applying the permutation on itself for N times and then applying it on the arr[]. Now, we can use binary exponentiation to apply the permutation on itself and then apply it on the arr[] to get the final permutation.
Step-by-step Algorithm:
- Define a function permute(S, P) that applies the permutation P to the array arr[] once.
- Now, use binary exponentiation to apply the permutation P to a array arr[] for K times.
- Check if K is odd, then apply permutation P to arr[].
- Apply Permutation P to itself and store it to P.
- Divide K by 2 and store it to K.
- Return the final array arr[].
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
// binary exponentiation
void permute(vector<int>& arr, vector<int>& P)
{
vector<int> temp(arr.size());
for (int i = 1; i < arr.size(); i++) {
temp[i] = arr[P[i]];
}
for (int i = 1; i < arr.size(); i++)
arr[i] = temp[i];
}
// Function to apply Permutation P to array arr[]
// K number of times
void solve(vector<int>& arr, vector<int>& P, int K)
{
while (K) {
if (K & 1)
// apply permutation on the sequence
permute(arr, P);
// apply permutation on itself
permute(P, P);
K >>= 1;
}
}
int main()
{
vector<int> P{ 0, 2, 3, 4, 1 };
vector<int> arr{ 0, 2, 1, 3, 4 };
int K = 3;
solve(arr, P, K);
for (int i = 1; i < arr.size(); i++)
cout << arr[i] << " ";
return 0;
}
import java.util.Arrays;
public class PermutationExample {
// Binary exponentiation
static void permute(int[] arr, int[] P) {
int[] temp = new int[arr.length];
for (int i = 1; i < arr.length; i++) {
temp[i] = arr[P[i]];
}
System.arraycopy(temp, 1, arr, 1, arr.length - 1);
}
// Function to apply Permutation P to array arr[]
// K number of times
static void solve(int[] arr, int[] P, int K) {
while (K > 0) {
if ((K & 1) == 1)
// apply permutation on the sequence
permute(arr, P);
// apply permutation on itself
permute(P, P);
K >>= 1;
}
}
public static void main(String[] args) {
int[] P = {0, 2, 3, 4, 1};
int[] arr = {0, 2, 1, 3, 4};
int K = 3;
solve(arr, P, K);
for (int i = 1; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by shivamgupta0987654321
# Function for binary exponentiation
def permute(arr, P):
temp = [0] * len(arr)
for i in range(1, len(arr)):
temp[i] = arr[P[i]]
for i in range(1, len(arr)):
arr[i] = temp[i]
# Function to apply permutation P to array arr K number of times
def solve(arr, P, K):
while K:
if K & 1:
# Apply permutation on the sequence
permute(arr, P)
# Apply permutation on itself
permute(P, P)
K >>= 1
if __name__ == "__main__":
P = [0, 2, 3, 4, 1]
arr = [0, 2, 1, 3, 4]
K = 3
solve(arr, P, K)
for i in range(1, len(arr)):
print(arr[i], end=" ")
# this code is contributed by shivamgupta0987654321
using System;
using System.Collections.Generic;
class Program {
// Binary exponentiation
static void Permute(List<int> arr, List<int> P)
{
List<int> temp = new List<int>(arr.Count);
for (int i = 0; i < arr.Count; i++) {
temp.Add(arr[P[i]]);
}
for (int i = 0; i < arr.Count; i++) {
arr[i] = temp[i];
}
}
// Function to apply Permutation P to array arr[]
// K number of times
static void Solve(List<int> arr, List<int> P, int K)
{
while (K > 0) {
if ((K & 1) == 1) {
// Apply permutation on the sequence
Permute(arr, P);
}
// Apply permutation on itself
Permute(P, P);
K >>= 1;
}
}
static void Main()
{
List<int> P = new List<int>{ 0, 2, 3, 4, 1 };
List<int> arr = new List<int>{ 0, 2, 1, 3, 4 };
int K = 3;
Solve(arr, P, K);
for (int i = 1; i < arr.Count; i++) {
Console.Write(arr[i] + " ");
}
}
}
// This code is contributed by shivamgupta0987654321
// JavaScript Implementation
function permute(arr, P) {
let temp = new Array(arr.length);
for (let i = 1; i < arr.length; i++) {
temp[i] = arr[P[i]];
}
for (let i = 1; i < arr.length; i++) {
arr[i] = temp[i];
}
}
function solve(arr, P, K) {
while (K) {
if (K & 1) {
permute(arr, P);
}
permute(P, P);
K >>= 1;
}
}
let P = [0, 2, 3, 4, 1];
let arr = [0, 2, 1, 3, 4];
let K = 3;
solve(arr, P, K);
for (let i = 1; i < arr.length; i++) {
console.log(arr[i]);
}
// This code is contributed by Tapesh(tapeshdu420)
Time Complexity: O(N * log(K)), where N is the length of input Sequence S and K is the number of times Permutation P is to be applied to Sequence S.
Auxiliary Space: O(N)
|
