Compute permutations of a string with unique and duplicate characters

Permutations.java

/* File:    Permutations.java
 * Created: 10/1/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */


import java.util.*;

//=======================================================================================

/**
 * @author Sabbir Manandhar [email protected]
 * @version 1.0
 */
public class Permutations {

  public static void main(String[] args) {
    List<String> permutations = permutationWithoutDuplicates("ABCD");
    for (String permutation : permutations)
      System.out.println(permutation);

    System.out.println();

    permutations = permuteWithDuplicates("AAABB");
    for (String permutation : permutations)
      System.out.println(permutation);
  } // main

  //-------------------------------------------------------------------------------------

  //------ Solution 1: For Input with Unique Characters Only -----------
  /**
   * Computes permutation of given string without any duplicate characters.
   * For string duplicate character, results will contain duplicate entries.
   * @param s input string
   * @return List of permutations
   */
  public static List<String> permutationWithoutDuplicates(String s) {
    char[] chars = s.toCharArray();
    List<String> permutations = new ArrayList<>();
    permutationWithoutDuplicatesHelper(chars, 0, permutations);
    return permutations;
  } // permutationWithoutDuplicates

  //-------------------------------------------------------------------------------------

  /**
   * Recursive helper method to compute permutations of a character array without duplicates.
   * @param chars input character array
   * @param cursor pointer to current location considered. Characters before this pointer and kept fixed.
   * @param permutations List holding resulting permutations
   */
  private static void permutationWithoutDuplicatesHelper(char[] chars, int cursor, List<String> permutations) {
    if (cursor == chars.length) {
      permutations.add(new String(chars));
      return;
    }

    for (int i = cursor; i < chars.length; i++) {
      swap(chars, cursor, i);
       // keep the selected character fixed and compute permutations of remaining characters
      permutationWithoutDuplicatesHelper(chars, cursor + 1, permutations);
      swap(chars, cursor, i);
    }
  } // permutationWithoutDuplicatesHelper

  //-------------------------------------------------------------------------------------

  /**
   * Utility method to swap two characters in the given character array.
   * @param chars input character array
   * @param i first index to swap.
   * @param j second index to swap.
   */
  private static void swap(char[] chars, int i, int j) {
    if (i == j) return;
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
  } // swap

  //------ END Solution 1 ---------------------------------------------------------------

  //-------------------------------------------------------------------------------------

  //------ Solution 2: For Input with Duplicate Characters ------------------------------

  /**
   * Computes permutation of an string with Duplicate characters.
   * Obviously, it will also work for the string with unique characters.
   * @param s input string.
   * @return Permutations of given input.
   */
  public static List<String> permuteWithDuplicates(String s) {
    char[] chars = s.toCharArray();
    Map<Character, Integer> frequencyMap = createFrequencyMap(chars);
    List<String> results = new ArrayList<>();
    permuteWithDuplicatesHelper(frequencyMap, new char[s.length()], 0, results);
    return results;
  } // permuteWithDuplicates

  //-------------------------------------------------------------------------------------

  /**
   * Recursive helper method to compute permutations of a string with duplicate characters.
   * @param frequencyMap Map holding character counts of input.
   * @param permutation current permutation
   * @param cursor current location in permutation
   * @param results List of all permutations of input.
   */
  private static void permuteWithDuplicatesHelper(Map<Character, Integer> frequencyMap, char[] permutation, int cursor, List<String> results) {
    if (cursor == permutation.length) {
      results.add(new String(permutation));
      return;
    }

    for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
      if (entry.getValue() > 0) {
        permutation[cursor] = entry.getKey();
        entry.setValue(entry.getValue() - 1);
        permuteWithDuplicatesHelper(frequencyMap, permutation, cursor + 1, results);
        entry.setValue(entry.getValue() + 1);
      }
    }
  } // permuteWithDuplicatesHelper

  //-------------------------------------------------------------------------------------

  /**
   * Utility method to create character counts as a Map.
   * @param chars input character array
   * @return Character Counts Map.
   */
  private static Map<Character, Integer> createFrequencyMap(char[] chars) {
    Map<Character, Integer> result = new HashMap<>();
    for (Character c : chars) {
      if (result.containsKey(c)) {
        result.put(c, result.get(c) + 1);
      } else {
        result.put(c, 1);
      }
    }
    return result;
  } // createFrequencyMap

  //------ END Solution 2 ---------------------------------------------------------------

} // Permutations