Posted on by Kalkicode
Code Number

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

  1. 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.
  2. 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 the permutation function with the next number.
  3. 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

  1. multiplier(num): This function calculates the multiplier needed to find cyclic permutations. It iterates through the digits of the input number num and calculates the multiplier by raising 10 to the power of the number of digits in num. For example, if num is 12345, the multiplier would be 100000.

  2. 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 the multiplier 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 of num, multiplying it by the multiplier, and adding the remaining digits to the end of this number. For example, if num 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 new num.

  3. 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:

  1. multiplier(num): This function iterates through the digits of the input number num to find the multiplier. The number of digits in num is proportional to its logarithm with base 10. Therefore, the time complexity of this function is O(log(num)).

  2. permutation(num, actual, multiply): This function is a recursive function that explores all the cyclic permutations of the input number num. It continues to call itself until it reaches the original actual 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)).

  3. cyclicPermutations(num): This function first calls the multiplier function, which has a time complexity of O(log(num)), and then it calls the permutation 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:

  1. For cyclicPermutations(76832):

    • The original number is 76832.
    • The cyclic permutations are 76832, 27683, 32768, 83276, and 68327.

  2. For cyclicPermutations(123456):

    • The original number is 123456.
    • The cyclic permutations are 123456, 612345, 561234, 456123, 345612, and 234561.

  3. 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

Comment

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





Categories
Relative Post