Python3 Program to Print all possible rotations of a given Array
Given an integer array arr[] of size N, the task is to print all possible rotations of the array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: {1, 2, 3, 4}, {4, 1, 2, 3}, {3, 4, 1, 2}, {2, 3, 4, 1}
Explanation:
Initial arr[] = {1, 2, 3, 4}
After first rotation arr[] = {4, 1, 2, 3}
After second rotation arr[] = {3, 4, 1, 2}
After third rotation arr[] = {2, 3, 4, 1}
After fourth rotation, arr[] returns to its original form.
Input: arr[] = [1]
Output: [1]
Approach:
Follow the steps below to solve the problem:
- Generate all possible rotations of the array, by performing a left rotation of the array one by one.
- Print all possible rotations of the array until the same rotation of array is encountered.
Below is the implementation of the above approach :
Python
# Python program to print # all possible rotations # of the given array # Function to reverse array # between indices s and e def reverse(arr, s, e): while s < e: tem = arr[s] arr[s] = arr[e] arr[e] = tem s = s + 1 e = e - 1 # Function to generate all # possible rotations of array def fun(arr, k): n = len (arr) - 1 # k = k % n v = n - k if v> = 0 : reverse(arr, 0 , v) reverse(arr, v + 1 , n) reverse(arr, 0 , n) return arr # Driver Code arr = [ 1 , 2 , 3 , 4 ] for i in range ( 0 , len (arr)): count = 0 p = fun(arr, i) print (p, end = " " ) |
[1, 2, 3, 4] [4, 1, 2, 3] [2, 3, 4, 1] [3, 4, 1, 2]
Time Complexity: O (N2)
Auxiliary Space: O (1)
Approach 2: Follow the steps below to solve the problem:
- Define the Main class.
- Define the main method which takes args as input.
- Create the arr array and get its length n.
- Create the rotatedArr array with length 2*n and fill it with zeroes.
- Copy the arr array twice into the rotatedArr array.
- Loop over the n possible rotations.
- For each rotation, print a “[” character.
- Loop over the elements of the rotated array.
- Print each element followed by a space (if it’s not the last element in the rotated array).
- After the loop, print a “]” character followed by a space.
- Run the main method if the script is being executed as the main module.
Below is the implementation of the above approach :
Python3
class Main: def main(args): arr = [ 1 , 2 , 3 , 4 ] n = len (arr) rotatedArr = [ 0 ] * ( 2 * n) # Copy the array twice into the rotatedArr for i in range (n): rotatedArr[i] = arr[i] rotatedArr[i + n] = arr[i] # Generate all possible rotations for i in range (n): print ( "[" , end = "") for j in range (i, i + n): print (rotatedArr[j], end = "") if j ! = i + n - 1 : print ( " " , end = "") print ( "] " , end = "") # Nikunj Sonigara if __name__ = = "__main__" : Main.main( None ) |
[1 2 3 4] [2 3 4 1] [3 4 1 2] [4 1 2 3]
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us