Generate a circular permutation with number of mismatching bits between pairs of adjacent elements exactly 1
Given two integers N and S, the task is to find a circular permutation of numbers from the range [0, 2(N – 1)], starting with S such that the count of mismatching bits between any pair of adjacent numbers is one.
Examples:
Input: N = 2, S = 3
Output: [3, 2, 0, 1]
Explanation:
The binary representation of numbers 3, 2, 0 and 1 are “11”, “10”, “01” and “00” respectively.
Therefore, arranging them in the order [3, 2, 0, 1] ensures that the number of bit differences between each pair of adjacent elements (circular) is 1.Input: N = 3, S = 2
Output: [2, 6, 7, 5, 4, 0, 1, 3]
Approach: The given problem can be solved based on the following observations:
- A simple observation is that the numbers in the range [2i, 2i + 1 – 1] can be obtained in their natural order by placing ‘1’s before each number in the range [0, 2i – 1].
- Therefore, the problem can be solved recursively by adding ‘1’ before each number before 2i – 1th index and reversing it before appending the new numbers to their permutation.
Follow the steps below to solve the problem:
- Initialize a list, say res, to store the required permutation.
- Initialize an integer, say index, to store the position of S in the permutation starting with 0.
- Iterate over the range [0, N – 1] and traverse the array res[] in reverse order and check if the sum of the current number and 2i is S or not. If found to be true, then update index with the current index of res and append the current number + 2i to the list res.
- Rotate the list res[] by index positions.
- After completing the above steps, print the list res[] as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the permutation of // integers from a given range such that // number of mismatching bits between // pairs of adjacent elements is 1 vector< int > circularPermutation( int n, int start) { // Initialize an arrayList to // store the resultant permutation vector< int > res = {0}; vector< int > ret; // Store the index of rotation int index = -1; // Iterate over the range [0, N - 1] for ( int k = 0, add = 1 << k; k < n; k++, add = 1 << k) { // Traverse all the array elements // up to (2 ^ k)-th index in reverse for ( int i = res.size() - 1; i >= 0; i--) { // If current element is S if (res[i] + add == start) index = res.size(); res.push_back(res[i] + add); } } // Check if S is zero if (start == 0) return res; // Rotate the array by index // value to the left while (ret.size() < res.size()) { ret.push_back(res[index]); index = (index + 1) % res.size(); } return ret; } // Driver Code int main() { int N = 2, S = 3; vector< int > print = circularPermutation(N, S); cout << "[" ; for ( int i = 0; i < print.size() - 1; i++ ) { cout << print[i] << ", " ; } cout << print[print.size() - 1] << "]" ; return 0; } // This code is contributed by susmitakundugoaldanga |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to find the permutation of // integers from a given range such that // number of mismatching bits between // pairs of adjacent elements is 1 public static List<Integer> circularPermutation( int n, int start) { // Initialize an arrayList to // store the resultant permutation List<Integer> res = new ArrayList<>(List.of( 0 )), ret = new ArrayList<>(); // Store the index of rotation int index = - 1 ; // Iterate over the range [0, N - 1] for ( int k = 0 , add = 1 << k; k < n; k++, add = 1 << k) { // Traverse all the array elements // up to (2 ^ k)-th index in reverse for ( int i = res.size() - 1 ; i >= 0 ; i--) { // If current element is S if (res.get(i) + add == start) index = res.size(); res.add(res.get(i) + add); } } // Check if S is zero if (start == 0 ) return res; // Rotate the array by index // value to the left while (ret.size() < res.size()) { ret.add(res.get(index)); index = (index + 1 ) % res.size(); } return ret; } // Driver Code public static void main(String[] args) { int N = 2 , S = 3 ; System.out.println( circularPermutation(N, S)); } } |
Python3
# Python3 program for the above approach # Function to find the permutation of # integers from a given range such that # number of mismatching bits between # pairs of adjacent elements is 1 def circularPermutation(n, start): # Initialize an arrayList to # store the resultant permutation res = [ 0 ] ret = [] # Store the index of rotation index, add = - 1 , 1 # Iterate over the range [0, N - 1] for k in range (n): add = 1 <<k # Traverse all the array elements # up to (2 ^ k)-th index in reverse for i in range ( len (res) - 1 , - 1 , - 1 ): # If current element is S if (res[i] + add = = start): index = len (res) res.append(res[i] + add) add = 1 << k # Check if S is zero if (start = = 0 ): return res # Rotate the array by index # value to the left while ( len (ret) < len (res)): ret.append(res[index]) index = (index + 1 ) % len (res) return ret # Driver Code if __name__ = = '__main__' : N,S = 2 , 3 print (circularPermutation(N, S)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the permutation of // integers from a given range such that // number of mismatching bits between // pairs of adjacent elements is 1 public static List< int > circularPermutation( int n, int start) { // Initialize an arrayList to // store the resultant permutation List< int > res = new List< int >(){0}; List< int > ret = new List< int >(); // Store the index of rotation int index = -1; // Iterate over the range [0, N - 1] for ( int k = 0, add = 1 << k; k < n; k++, add = 1 << k) { // Traverse all the array elements // up to (2 ^ k)-th index in reverse for ( int i = res.Count - 1; i >= 0; i--) { // If current element is S if (res[i] + add == start) index = res.Count; res.Add(res[i] + add); } } // Check if S is zero if (start == 0) return res; // Rotate the array by index // value to the left while (ret.Count < res.Count) { ret.Add(res[index]); index = (index + 1) % res.Count; } return ret; } // Driver Code static public void Main () { int N = 2, S = 3; List< int > print = circularPermutation(N, S); Console.Write( "[" ); for ( int i = 0; i < print.Count - 1; i++ ) { Console.Write(print[i] + ", " ); } Console.Write(print[print.Count-1] + "]" ); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program for the above approach // Function to find the permutation of // integers from a given range such that // number of mismatching bits between // pairs of adjacent elements is 1 function circularPermutation(n, start) { // Initialize an arrayList to // store the resultant permutation var res = [0]; var ret = []; // Store the index of rotation var index = -1; // Iterate over the range [0, N - 1] for ( var k = 0, add = 1 << k; k < n; k++, add = 1 << k) { // Traverse all the array elements // up to (2 ^ k)-th index in reverse for ( var i = res.length - 1; i >= 0; i--) { // If current element is S if (res[i] + add == start) index = res.length; res.push(res[i] + add); } } // Check if S is zero if (start == 0) return res; // Rotate the array by index // value to the left while (ret.length < res.length) { ret.push(res[index]); index = (index + 1) % res.length; } return ret; } // Driver Code var N = 2, S = 3; var print = circularPermutation(N, S); document.write( "[" ); for ( var i = 0; i < print.length - 1; i++ ) { document.write( print[i] + ", " ); } document.write( print[print.length - 1] + "]" ); </script> |
[3, 2, 0, 1]
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us