Generate all cyclic permutations of a number
The given problem is to generate all cyclic permutations of a number. A cyclic permutation of a number is a permutation in which the digits of the number are shifted to the left or right, and the number itself is rotated in a circular manner. For example, for the number 123, the cyclic permutations would be 231 and 312. The objective is to find all possible cyclic permutations of a given number and print them.
Example
Let's take the number 12345 as an example. The cyclic permutations of this number would be:
- 12345
- 51234
- 45123
- 34512
- 23451
Pseudocode
- Define a function
multiplier(num)
to calculate the multiplier needed to find cyclic permutations. It calculates 10 raised to the power of the number of digits in the input number. - Define a function
permutation(num, actual, multiply)
to find and print cyclic permutations of the number.- Print the current number
num
. - Calculate the next number in the cyclic permutation by shifting the last digit to the front and multiplying it by the multiplier. Add the remaining digits to the end of this number.
- If the next number is not equal to the original
actual
number, recursively call thepermutation
function with the next number.
- Print the current number
- Define the main function
cyclicPermutations(num)
to handle the request of finding cyclic permutations for a given number.- Check if the input number is negative, if so, return.
- Calculate the multiplier for the input number using the
multiplier
function. - Print the header for the output.
- Call the
permutation
function with the input number, the original number, and the calculated multiplier.
Algorithm
Function multiplier(num):
ans = 0
while num is not 0:
if ans is 0:
ans = 1
else:
ans = ans * 10
num = num / 10
return ans
Function permutation(num, actual, multiply):
Print num
next = (num % 10) * multiply + (num / 10)
if next is not equal to actual:
Call permutation(next, actual, multiply)
Function cyclicPermutations(num):
if num < 0:
Return
multiply = multiplier(num)
Print "Cyclic Permutation Of Number", num, "are"
Call permutation(num, num, multiply)
Main function:
Call cyclicPermutations(76832)
Call cyclicPermutations(123456)
Call cyclicPermutations(420)
Explanation
-
multiplier(num)
: This function calculates the multiplier needed to find cyclic permutations. It iterates through the digits of the input numbernum
and calculates the multiplier by raising 10 to the power of the number of digits innum
. For example, ifnum
is 12345, the multiplier would be 100000. -
permutation(num, actual, multiply)
: This function finds and prints cyclic permutations of the number. It takes three parameters:num
: The current number in the cyclic permutation.actual
: The original number that is being cyclically permuted.multiply
: The multiplier calculated using themultiplier
function.
The function prints the current number
num
and then calculates the next number in the cyclic permutation. It does this by taking the last digit ofnum
, multiplying it by the multiplier, and adding the remaining digits to the end of this number. For example, ifnum
is 12345 and the multiplier is 100000, the next number would be (5 * 100000) + 1234 = 51234.If the next number is not equal to the original
actual
number, it means there are more cyclic permutations to find, so the function calls itself recursively with the next number as the newnum
. -
cyclicPermutations(num)
: This function handles the request of finding cyclic permutations for a given number. It takes one parameter:num
: The number for which cyclic permutations are to be found.
The function first checks if the input number is negative. If it is, then there are no cyclic permutations to find for a negative number, so the function returns.
Next, the function calculates the multiplier for the input number using the
multiplier
function. It then prints the header for the output indicating which number's cyclic permutations are being printed.Finally, the function calls the
permutation
function with the input number, the original number (which remains unchanged during the recursive calls), and the calculated multiplier to find and print all the cyclic permutations.
Code Solution
Here given code implementation process.
/*
C Program
Generate all cyclic permutations of a number
*/
#include <stdio.h>
// Get number multiplier to permutations
int multiplier(int num)
{
int ans = 0;
while (num != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans *10;
}
num /= 10;
}
return ans;
}
// Find all cyclic permutations in number form
void permutation(int num, int actual, int multiply)
{
printf(" %d\n", num);
int next = (num % 10) *multiply + (num / 10);
if (next != actual)
{
permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
void cyclicPermutations(int num)
{
if (num < 0)
{
// When number is less then zero
return;
}
int multiply = multiplier(num);
printf("\n Cyclic Permutation Of Number %d are \n", num);
permutation(num, num, multiply);
}
int main()
{
// Test
cyclicPermutations(76832);
cyclicPermutations(123456);
cyclicPermutations(420);
return 0;
}
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
/*
Java Program
Generate all cyclic permutations of a number
*/
class Permutations
{
// Get number multiplier to permutations
public int multiplier(int num)
{
int ans = 0;
while (num != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans * 10;
}
num /= 10;
}
return ans;
}
// Find all cyclic permutations in number form
public void permutation(int num, int actual, int multiply)
{
System.out.print(" " + num + "\n");
int next = (num % 10) * multiply + (num / 10);
if (next != actual)
{
permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
public void cyclicPermutations(int num)
{
if (num < 0)
{
// When number is less then zero
return;
}
int multiply = multiplier(num);
System.out.print("\n Cyclic Permutation Of Number " + num + " are \n");
permutation(num, num, multiply);
}
public static void main(String[] args)
{
Permutations task = new Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
}
}
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Generate all cyclic permutations of a number
*/
class Permutations
{
public:
// Get number multiplier to permutations
int multiplier(int num)
{
int ans = 0;
while (num != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans *10;
}
num /= 10;
}
return ans;
}
// Find all cyclic permutations in number form
void permutation(int num, int actual, int multiply)
{
cout << " " << num << "\n";
int next = (num % 10) *multiply + (num / 10);
if (next != actual)
{
this->permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
void cyclicPermutations(int num)
{
// When number is less then zero
if (num < 0)
{
return;
}
int multiply = this->multiplier(num);
cout << "\n Cyclic Permutation Of Number " << num << " are \n";
this->permutation(num, num, multiply);
}
};
int main()
{
Permutations task = Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
return 0;
}
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
// Include namespace system
using System;
/*
C# Program
Generate all cyclic permutations of a number
*/
public class Permutations
{
// Get number multiplier to permutations
public int multiplier(int num)
{
int ans = 0;
while (num != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans * 10;
}
num /= 10;
}
return ans;
}
// Find all cyclic permutations in number form
public void permutation(int num, int actual, int multiply)
{
Console.Write(" " + num + "\n");
int next = (num % 10) * multiply + (num / 10);
if (next != actual)
{
permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
public void cyclicPermutations(int num)
{
// When number is less then zero
if (num < 0)
{
return;
}
int multiply = multiplier(num);
Console.Write("\n Cyclic Permutation Of Number " + num + " are \n");
permutation(num, num, multiply);
}
public static void Main(String[] args)
{
Permutations task = new Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
}
}
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
<?php
/*
Php Program
Generate all cyclic permutations of a number
*/
class Permutations
{
// Get number multiplier to permutations
public function multiplier($num)
{
$ans = 0;
while ($num != 0)
{
if ($ans == 0)
{
$ans = 1;
}
else
{
$ans = $ans * 10;
}
$num = intval($num / 10);
}
return $ans;
}
// Find all cyclic permutations in number form
public function permutation($num, $actual, $multiply)
{
echo " ". $num ."\n";
$next = ($num % 10) * $multiply + (intval($num / 10));
if ($next != $actual)
{
$this->permutation($next, $actual, $multiply);
}
}
// Handles the request of finding cyclic Permutation
public function cyclicPermutations($num)
{
// When number is less then zero
if ($num < 0)
{
return;
}
$multiply = $this->multiplier($num);
echo "\n Cyclic Permutation Of Number ". $num ." are \n";
$this->permutation($num, $num, $multiply);
}
}
function main()
{
$task = new Permutations();
// Test
$task->cyclicPermutations(76832);
$task->cyclicPermutations(123456);
$task->cyclicPermutations(420);
}
main();
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
/*
Node Js Program
Generate all cyclic permutations of a number
*/
class Permutations
{
// Get number multiplier to permutations
multiplier(num)
{
var ans = 0;
while (num != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans * 10;
}
num = parseInt(num / 10);
}
return ans;
}
// Find all cyclic permutations in number form
permutation(num, actual, multiply)
{
process.stdout.write(" " + num + "\n");
var next = (num % 10) * multiply + (parseInt(num / 10));
if (next != actual)
{
this.permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
cyclicPermutations(num)
{
// When number is less then zero
if (num < 0)
{
return;
}
var multiply = this.multiplier(num);
process.stdout.write("\n Cyclic Permutation Of Number " + num + " are \n");
this.permutation(num, num, multiply);
}
}
function main()
{
var task = new Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
}
main();
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
# Python 3 Program
# Generate all cyclic permutations of a number
class Permutations :
# Get number multiplier to permutations
def multiplier(self, num) :
ans = 0
while (num != 0) :
if (ans == 0) :
ans = 1
else :
ans = ans * 10
num = int(num / 10)
return ans
# Find all cyclic permutations in number form
def permutation(self, num, actual, multiply) :
print(" ", num )
next = (num % 10) * multiply + (int(num / 10))
if (next != actual) :
self.permutation(next, actual, multiply)
# Handles the request of finding cyclic Permutation
def cyclicPermutations(self, num) :
if (num < 0) :
# When number is less then zero
return
multiply = self.multiplier(num)
print("\n Cyclic Permutation Of Number ", num ," are ")
self.permutation(num, num, multiply)
def main() :
task = Permutations()
# Test
task.cyclicPermutations(76832)
task.cyclicPermutations(123456)
task.cyclicPermutations(420)
if __name__ == "__main__": main()
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
# Ruby Program
# Generate all cyclic permutations of a number
class Permutations
# Get number multiplier to permutations
def multiplier(num)
ans = 0
while (num != 0)
if (ans == 0)
ans = 1
else
ans = ans * 10
end
num /= 10
end
return ans
end
# Find all cyclic permutations in number form
def permutation(num, actual, multiply)
print(" ", num ,"\n")
nextNum = (num % 10) * multiply + (num / 10)
if (nextNum != actual)
self.permutation(nextNum, actual, multiply)
end
end
# Handles the request of finding cyclic Permutation
def cyclicPermutations(num)
if (num < 0)
# When number is less then zero
return
end
multiply = self.multiplier(num)
print("\n Cyclic Permutation Of Number ", num ," are \n")
self.permutation(num, num, multiply)
end
end
def main()
task = Permutations.new()
# Test
task.cyclicPermutations(76832)
task.cyclicPermutations(123456)
task.cyclicPermutations(420)
end
main()
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
/*
Scala Program
Generate all cyclic permutations of a number
*/
class Permutations
{
// Get number multiplier to permutations
def multiplier(num: Int): Int = {
var n = num;
var ans: Int = 0;
while (n != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans * 10;
}
n = (n / 10).toInt;
}
return ans;
}
// Find all cyclic permutations in number form
def permutation(num: Int, actual: Int, multiply: Int): Unit = {
print(" " + num + "\n");
var next: Int = (num % 10) * multiply + ((num / 10).toInt);
if (next != actual)
{
this.permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
def cyclicPermutations(num: Int): Unit = {
// When number is less then zero
if (num < 0)
{
return;
}
var multiply: Int = this.multiplier(num);
print("\n Cyclic Permutation Of Number " + num + " are \n");
this.permutation(num, num, multiply);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Permutations = new Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
}
}
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
/*
Swift 4 Program
Generate all cyclic permutations of a number
*/
class Permutations
{
// Get number multiplier to permutations
func multiplier(_ num: Int)->Int
{ var n = num;
var ans: Int = 0;
while (n != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans * 10;
}
n /= 10;
}
return ans;
}
// Find all cyclic permutations in number form
func permutation(_ num: Int, _ actual: Int, _ multiply: Int)
{
print(" ", num );
let next: Int = (num % 10) * multiply + (num / 10);
if (next != actual)
{
self.permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
func cyclicPermutations(_ num: Int)
{
// When number is less then zero
if (num < 0)
{
return;
}
let multiply: Int = self.multiplier(num);
print("\n Cyclic Permutation Of Number ", num ," are ");
self.permutation(num, num, multiply);
}
}
func main()
{
let task: Permutations = Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
}
main();
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
/*
Kotlin Program
Generate all cyclic permutations of a number
*/
class Permutations
{
// Get number multiplier to permutations
fun multiplier(num: Int): Int
{
var n = num;
var ans: Int = 0;
while (n != 0)
{
if (ans == 0)
{
ans = 1;
}
else
{
ans = ans * 10;
}
n /= 10;
}
return ans;
}
// Find all cyclic permutations in number form
fun permutation(num: Int, actual: Int, multiply: Int): Unit
{
print(" " + num + "\n");
var next: Int = (num % 10) * multiply + (num / 10);
if (next != actual)
{
this.permutation(next, actual, multiply);
}
}
// Handles the request of finding cyclic Permutation
fun cyclicPermutations(num: Int): Unit
{
// When number is less then zero
if (num < 0)
{
return;
}
var multiply: Int = this.multiplier(num);
print("\n Cyclic Permutation Of Number " + num + " are \n");
this.permutation(num, num, multiply);
}
}
fun main(args: Array < String > ): Unit
{
var task: Permutations = Permutations();
// Test
task.cyclicPermutations(76832);
task.cyclicPermutations(123456);
task.cyclicPermutations(420);
}
Output
Cyclic Permutation Of Number 76832 are
76832
27683
32768
83276
68327
Cyclic Permutation Of Number 123456 are
123456
612345
561234
456123
345612
234561
Cyclic Permutation Of Number 420 are
420
42
204
Time Complexity
The time complexity of the given code can be analyzed as follows:
-
multiplier(num)
: This function iterates through the digits of the input numbernum
to find the multiplier. The number of digits innum
is proportional to its logarithm with base 10. Therefore, the time complexity of this function is O(log(num)). -
permutation(num, actual, multiply)
: This function is a recursive function that explores all the cyclic permutations of the input numbernum
. It continues to call itself until it reaches the originalactual
number again. The number of cyclic permutations of any number is equal to the number of digits in that number, which is again proportional to its logarithm with base 10. Therefore, the time complexity of this function is O(log(num)). -
cyclicPermutations(num)
: This function first calls themultiplier
function, which has a time complexity of O(log(num)), and then it calls thepermutation
function, which also has a time complexity of O(log(num)). Therefore, the overall time complexity of this function is O(log(num)).
Since all the functions have a time complexity of O(log(num)), the overall time complexity of the given code is also O(log(num)).
Resultant Output Explanation
The code generates all the cyclic permutations of the provided numbers and prints them to the console. Let's go through the output for the provided test cases:
-
For
cyclicPermutations(76832)
:- The original number is 76832.
- The cyclic permutations are 76832, 27683, 32768, 83276, and 68327.
-
For
cyclicPermutations(123456)
:- The original number is 123456.
- The cyclic permutations are 123456, 612345, 561234, 456123, 345612, and 234561.
-
For
cyclicPermutations(420)
:- The original number is 420.
- The cyclic permutations are 420, 42, and 204.
The code successfully generates and prints all the cyclic permutations for the given numbers.
Finally
The given code effectively generates all the cyclic permutations of a given number. It uses recursive functions to explore all the possible cyclic permutations and prints them to the console. The code's time complexity is O(log(num)), where num is the input number, making it efficient for practical purposes. The article provides a clear explanation of the problem, the code's logic, and the output
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment