Generate unique permutation in Java

We already saw how to generate all possible permutation in java. Today we will modify our algorithm to remove duplicate entries to keep only unique permutation.

For an example, if the given string is: 112, our program will generate:

112
121
211



Algorithm in brief:

We will use a recursive algorithm to achieve our solution. At each level, we need to check whatever the character is already processed or not. If already processed, we will ignore it.

For a clear understanding, please observe the image below. For the given string 1123, all possible permutations which start with 2 are:

2113
2131
2113 (Duplicate, 1 after 2 already processed in the previous step, we will ignore this 1 to process)
2131 (Duplicate, 1 after 2 already processed in the previous step, we will ignore this 1 to process)
2311
2311 (Duplicate, 1 after 3 already processed in the previous step, we will ignore this 1 to process)

Source code:

package com.monirthought.backtracking;

import java.util.Scanner;

/**
 * Generate all unique permutations of a given string.
 * 
 * @author Moniruzzaman Md
 *
 */
public class UniquePermutation {

 final private int MAXN = 7;
 private int[] flag = new int[MAXN];
 private String input = null;
 StringBuffer tempString = null;

 /**
  * Recursively generates all unique permutations.
  * 
  * @param index
  * @param level
  */
 private void generatePermutation(int index, int level) {

  tempString.setCharAt(level, input.charAt(index));

  StringBuffer alreadyTaken = new StringBuffer(input.length());

  flag[index] = 1;

  for (int i = 0; i < input.length(); i++) {
   if (flag[i] == 0) {
    if (-1 == alreadyTaken.indexOf(input.charAt(i) + "")) {
     generatePermutation(i, level + 1);
     alreadyTaken.append(input.charAt(i));
    }
   }
  }
  if (level == input.length() - 1) {
   System.out.println(tempString);
  }

  flag[index] = 0;

 }

 /**
  * Read Input from Console.
  */
 private void readInput() {
  Scanner scanner = new Scanner(System.in);
  this.input = scanner.nextLine();

  if (this.input.length() > 7) {
   System.exit(0);
  }
  this.tempString = new StringBuffer(this.input);
  StringBuffer alreadyTaken = new StringBuffer(input.length());

  for (int i = 0; i < this.input.length(); i++) {
   if (-1 == alreadyTaken.indexOf(input.charAt(i) + "")) {
    this.generatePermutation(i, 0);
    alreadyTaken.append(input.charAt(i));
   }
  }
  scanner.close();
 }

 public static void main(String[] args) {
  new UniquePermutation().readInput();
 }

}