Find the permutations of a string

Permutation represents the possible ways in which a set or number of things can be ordered or arranged.

For example,

for the string "abc", ["abc", "acb", "bac", "bca", "cab", "cba"] are the possible permutations.

Lets try to solve this problem using bottom-up approach.

Let P(data) represents Permutation of data, then

P("a") = ["a"]

P("b") = ["b"]

P("c") = ["c"]

P("ab") = "a" + P("b") = "a" + ["b"] = ["ab"] And

                  + "b" + P("a") = "b" + ["a"] = ["ba"]

                  = ["ab", "ba"]

Similarly

P("bc") = ["bc", "cb"]

P("ac") = ["ac", "ca"]                     

P("abc") = "a" + P("bc") = "a" + ["bc", "cb"] = ["abc", "acb"] And

                   + "b" + P("ac") = "b" + ["ac", "ca"] = ["bac", "bca"] And

                   + "c" + P("ab") = "c" + ["ab", "ba"] = ["cab", "cba"]

                   = ["abc", "acb", "bac", "bca", "cab", "cba"]

From the above example, we can deduce a base codition like below.

P(data) = data, if data length is equal to 1.

PermutationGenerator.java

package com.sample.app.generators;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Generate permutations of given string.
 * 
 * @author Krishna
 *
 */
public class PermutationGenerator {
 /**
  * Remove the character at given position.
  * 
  * @param str
  * @param position
  * @return
  */
 private static String removeCharacterAtPos(String str, int position) {
  return str.substring(0, position) + "" + str.substring(position + 1);
 }

 /**
  * Concatenate character to every element in permutations list and store the
  * final result in tmpList.
  * 
  * @param tmpList
  * @param charAt
  * @param permutations
  */
 private static void concat(List<String> tmpList, char charAt, List<String> permutations) {
  for (int i = 0; i < permutations.size(); i++) {
   tmpList.add(charAt + permutations.get(i));
  }
 }

 public static List<String> permutations(String data) {
  /* Base Condition */
  if (data.length() == 1) {
   return Arrays.asList(data);
  }

  List<String> tmpList = new ArrayList<>();
  for (int i = 0; i < data.length(); i++) {
   concat(tmpList, data.charAt(i), permutations(removeCharacterAtPos(data, i)));
  }

  return tmpList;
 }

}

Application.java

package com.sample.app;

import com.sample.app.generators.PermutationGenerator;

public class Application {

 public static void main(String args[]) {
  System.out.println(PermutationGenerator.permutations("abcd"));
 }

}

Output

[abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba]

Enhancing above application.

Lets try to enhance the above application.

For example, for the string "abcde", permutation calculation is like below.

P("abcd") = "a" + P("bcd")

                    = "b" + P("acd")

                    = "c" + P("abd")

                    = "d" + P("abc")

                   

As you observe above statements, P("cd") should be computed twice in P("bcd"), P("acd"), same is the case of P("bd"), P("ad"), p("ac"). If we reuse the previously computed values, then we can improve the performance.

PermutationGenerator.java

package com.sample.app.generators;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Generate permutations of given string.
 * 
 * @author Krishna
 *
 */
public class PermutationGenerator {

 private Map<String, List<String>> map = new HashMap<>();

 /**
  * Remove the character at given position.
  * 
  * @param str
  * @param position
  * @return
  */
 private static String removeCharacterAtPos(String str, int position) {
  return str.substring(0, position) + "" + str.substring(position + 1);
 }

 /**
  * Concatenate character to every element in permutations list and store the
  * final result in tmpList.
  * 
  * @param tmpList
  * @param charAt
  * @param permutations
  */
 private static void concat(List<String> tmpList, char charAt, List<String> permutations) {
  for (int i = 0; i < permutations.size(); i++) {
   tmpList.add(charAt + permutations.get(i));
  }
 }

 public List<String> permutations(String data) {
  List<String> computedResult = map.get(data);
  if (computedResult != null) {
   // System.out.println("Already computed for " + data);
   return computedResult;
  }

  /* Base Condition */
  if (data.length() == 1) {
   return Arrays.asList(data);
  }

  List<String> tmpList = new ArrayList<>();
  for (int i = 0; i < data.length(); i++) {
   concat(tmpList, data.charAt(i), permutations(removeCharacterAtPos(data, i)));

  }

  /* Store the computed permutations and reuse */
  if (map.get(data) == null) {
   map.put(data, tmpList);
  }
  return tmpList;
 }

}

Application.java

package com.sample.app;

import com.sample.app.generators.PermutationGenerator;

public class Application {

 public static void main(String args[]) {
  String targetStr = "abcd";
  PermutationGenerator permGen = new PermutationGenerator();
  System.out.println(permGen.permutations(targetStr));
 }

}

You may like

Interview Questions

Programming Questions

Miscellaneous

Find the missing element

Find the max product value of 3 numbers

Find the first element that appears an even number of times

Find the element that appears once in an array

Convert integers into roman equivalents

Count number of occurrences of a string