Permutation of Numbers in Java

In this section, we will create a Java program and find the permutation and cyclic permutation of a number. Before moving ahead in this section, first, we will understand permutation with examples.

Permutation

In mathematics, the permutation is a method or technique in which we can determine the possible arrangements in a set. The number of ways of selection and arrangement of items in which orders matters. In short, the permutation is the number of arrangements. While determining the permutation, keep order in mind. It is denoted by the letter P.

In other words, it is a technique by which we can arrange (or select) r objects out of given n objects in a particular order.

Mathematically, we can find the permutation of the numbers by using the following formula:

Permutation of Numbers in Java

Where,

P: P is the number of permutations.

n: n is the total number of objects in the set.

r: r is the number of choosing objects from the set.

!: The symbol denotes the factorial.

For example, if XYZ is a word then the possible permutations of the word will be:

XYZ, XZY, YXZ, YZX, ZXY, ZYX

Hence, we can arrange the word XYZ in six distinct ways.

Let’s see an example.

Example: There are six people participating in a skit. In how many ways first and the second prize can be awarded?

Solution:

Given:

n=6, r=2, P=?

According to the above formula:

Permutation of Numbers in Java

4, 3, 2, 1 are presented in both nominator and denominator so, they are canceled out.

P(6,2)=6*5

P(6,2)=30

Hence, there are 30 possible ways to award the first and second prizes.

Let’s implement the above approach in a Java program.

PermutationExample1.java

  import java.util.*;    public class PermutationExample1  {    public static void main(String args[])    {    //totalobjects=n, selectedobjects=r  int totalobjects, selectedobject, permutation, f1, f2;    //creating a constructor of the Scanner class  Scanner sc = new Scanner(System.in);    System.out.println(“Enter the Value of n and r: “);    //reading the value of n   totalobjects = sc.nextInt();    //reading the value of r  selectedobject = sc.nextInt();    f1 = totalobjects;    for (int i = totalobjects – 1; i >= 1; i–)    {    f1 = f1 * i;    }    int number;    number = totalobjects – selectedobject;    f2 = number;    for (int i = number – 1; i >= 1; i–)    {    //determining the factorial  f2 = f2 * i;    }    permutation = f1 / f2;    //prints the permutation  System.out.println(“The permutation of P(n, r) = “+permutation);    }    }    

Output:

Enter the Value of n and r:   7 4  The permutation of P(n, r) = 840

Let’s create another Java program and find the permutation of a number n greater than the number itself.

PermutationExample2.java

  public class PermutationExample2  {  //main() method  public static void main(String args[])   {  //the number to be permutate  int number = 123;  findPermutation(number);  }  //static method to find the permutation  static void findPermutation(int number)   {  int temp = number, count = 0;  //iteration over the specified digit   while (temp > 0)   {  //increments the count variable by 1 i the above condition returns true      count++;  //divides the variable temp by 10  temp = temp / 10;  }  //using vector to print the permutation of N  int[] num = new int[count];  // Store digits of N  // in the vector num  while (number > 0)  {  //finds the remainder and store the digit in vector num  num[count– – 1] = number % 10;  number = number / 10;  }  //iterate over each permutation and find the permutations that are greater than N  while (findsNextpermutation(num))   {    for (int i = 0; i < num.length; i++)  //print all the permutations of N  System.out.print(num[i]);  //throw the cursor to the new line  System.out.print(“n”);  }  }  //the user-defined function finds all the permutation greater than the number itself  static boolean findsNextpermutation(int[] p)   {  for (int a = p.length – 2; a >= 0; –a)  if (p[a] < p[a + 1])  for (int b = p.length – 1;; –b)  if (p[b] > p[a])   {  //swapping logic  int t = p[a];  p[a] = p[b];  p[b] = t;  for (++a, b = p.length – 1; a < b; ++a, –b)  {  //swapping logic  t = p[a];  p[a] = p[b];  p[b] = t;  }  return true;  }  return false;  }  }  

Output:

132  213  231  312  321

Using Heap Algorithm

It is an iterative algorithm. By using the heap algorithm, we can find all the permutations of n objects.

The algorithm generates (n-1)! permutations of the first n-1 elements, adjoining the last element to each of these. This will generate all of the permutations that end with the last element.
If n is odd, swap the first and last element and if n is even, then swapping the i^th element (i is the counter starting from 0) and the last element and repeat the above algorithm till i is less than n.
In each iteration, the algorithm will produce all the permutations that end with the current last element.

Let’s implement the algorithm in a Java program.

PermutationExample3.java

  public class PermutationExample3  {  //method to print permutations of specified array  void printPermutations(int array[], int n)  {  for (int i = 0; i < n; i++)  System.out.print(array[i] + ” “);  //throws the cursor to the next line  System.out.println();  }  //finds permutation using Heap Algorithm  void findPermutation(int array[], int size, int n)  {  // if size becomes 1, it prints the obtained permutation  if (size == 1)  printPermutations(array, n);  for (int i = 0; i < size; i++)   {  findPermutation(array, size – 1, n);  //if the length of the array is odd, it swaps the 0th element with the last element   if (size % 2 == 1)   {  //performing swapping  int temp = array[0];  array[0] = array[size – 1];  array[size – 1] = temp;  }  //if the size of the array is even, it swaps the ith element with the last element  else   {  //taking a temp variable for swapping  int temp;  //performing swapping   temp = array[i];  array[i] = array[size – 1];  array[size – 1] = temp;  }  }  }  //main() method  public static void main(String args[])  {  PermutationExample3 p = new PermutationExample3();  //defining an array whose permutation is to find  int array[] = { 8, 2, 6, 7 };  //calling the user-defined method  p.findPermutation(array, array.length, array.length);  }  }  

Output:

8 2 6 7   2 8 6 7   6 8 2 7   8 6 2 7   2 6 8 7   6 2 8 7   7 2 6 8   2 7 6 8   6 7 2 8   7 6 2 8   2 6 7 8   6 2 7 8   7 8 6 2   8 7 6 2   6 7 8 2   7 6 8 2   8 6 7 2   6 8 7 2   7 8 2 6   8 7 2 6   2 7 8 6   7 2 8 6   8 2 7 6   2 8 7 6

Using Recursive Algorithm

The recursive algorithm uses backtracking. It demines the permutation of numbers by swapping one element per iteration.

Permutation of Numbers in Java

Let’s implement the algorithm in a Java program.

PermutationExample4.java

  public class PermutationExample4   {   public static void main(String args[])   {   //string to permutate   String str = “come”;   //determines the length of the given string  int length = str.length();   PermutationExample4 per= new PermutationExample4();  //calling the method to find the permutation  per.permutation(str, 0, length-1);   }   //function that determines the permutations  //str: is the string to permutate  //si: is the starting index  //li: is the last index  private void permutation(String str, int si, int li)   {   if (si == li)   System.out.println(str);   else  {   for (int i = si; i <= li; i++)   {   //calling user-defined swapping method  str = swapChar(str,si,i);   //calling permutation() method  permutation(str, si+1, li);   str = swapChar(str,si,i);   }   }   }   //user-defined method to swap characters  public String swapChar(String str, int i, int j)   {   char temp;   //converts string into character array   char[] chArray = str.toCharArray();   temp = chArray[i] ;   chArray[i] = chArray[j];   chArray[j] = temp;   //returns string after swapping  return String.valueOf(chArray);   }   }   

Output:

come  coem  cmoe  cmeo  cemo  ceom  ocme  ocem  omce  omec  oemc  oecm  moce  moec  mcoe  mceo  meco  meoc  eomc  eocm  emoc  emco  ecmo  ecom

Randomized Algorithm

We can also apply the randomized algorithm for determining the permutation of numbers. It is used if the value of n is big. The algorithm generates the permutations by shuffling the array. For shuffling, the Java Collections class provides the shuffle() method.

The shuffle() method randomly permutates the specified List using a default source of randomness. It traverses the list in a backward (from the last element to the second element) direction. It randomly swaps the selected element with the current position. The method runs in linear time. The signature of the method is:

Generating Cyclic Permutations

A permutation composed of a single cycle is known as the cyclic permutation. It shifts all the elements of a set by a fixed offset. The technique can be applied to any integer to shift cyclically right or left by any given number of places. If a set has elements {a, b, c}, then:

Cyclic permutation one place left generates: {c, a, b}
Cyclic permutation one place right generates: {a, b, c}

Suppose n is a number whose cyclic permutation is to be found. We can find the cyclic permutation by using the following steps. It generates the next permutation.

  remainder = number % 10;  div = number / 10;  number = (pow(10, n – 1)) * remainder + div;  

We execute the above steps until we get the original number. As soon as, we get the original number, we stop performing the above steps and return the remainder.

For example, find the division of the following fractions:

2/7 = 0.285714…

4/7 = 0.571428…

1/7 = 0.142857…

Let’s create a Java program and generate all the possible cyclic permutations.

PermutationExample5.java

  public class PermutationExample5   {   //the function finds the total number of digits in a number   static int noOfDigits(int N)   {   int count = 0;   while (N>0)   {  //increments the variable count by 1 if n>0  count++;   //divides the variable n by 10   N = N / 10;   }   //returns the total number of digits  return count;   }   //the function generates the cyclic permutations  static void cyclicPermutation(int N)   {   int num = N;   int n = noOfDigits(N);   while (true)   {   System.out.println(num);   //the next three statements generate the cyclic permutations  int remainder = num % 10;   int dev = num / 10;   num = (int)((Math.pow(10, n – 1)) * remainder + dev);   //if the condition is true, it exits from the loop  if (num == N)   break;   }   }   //main() method   public static void main (String args[])   {   //number to permutate  int N = 9871;   //calling the user-defined method  cyclicPermutation(N);   }   }   

Output:

9871  1987  7198  8719

Next TopicMagic Number in Java

Permutation of Numbers in Java

Permutation of Numbers in Java

Permutation

Using Heap Algorithm

Using Recursive Algorithm

Randomized Algorithm

Generating Cyclic Permutations

Lombok Java

Polygonal Number in Java

You may also like