AdSense

Saturday, December 27, 2014

Generate all permutations

Given a string array ex: [1, 2, 3], find the permutation in best time.

Implement Next Permutation method.
Because we are doing in place permutation, be careful when pass to the result list.


import java.util.*; 
import org.apache.commons.lang3.ArrayUtils;
public class Permutation {
 public ArrayList generatePermutation (String[] array) {
  ArrayList rst = new ArrayList ();
  if (array == null)
   throw new NullPointerException("Null array!");
  if (array.length == 0)
   return rst;
  //I don't like to modify the original array;
  String[] input = new String[array.length];
  System.arraycopy(array, 0, input, 0, array.length);
  Arrays.sort(input);
  rst.add(ArrayUtils.addAll(input));
  while (nextPermutation(input)){
   /* if you don't want to use external library, 
    * change nextPermutation() return type to String[] and do arraycoppy
    * String[] output = new String[input.length];
    * System.arraycopy(input, 0, output, 0, input.length);
    * rst.add(output);*/
   rst.add(ArrayUtils.addAll(input));
   
  };
  return rst;
  
 }
 private boolean nextPermutation(String[] array) {
  int index = array.length - 1;
  while (array[index - 1].compareTo (array[index]) >= 0) {
   index--;
   if (index <= 0)
    return false;
  }
  int pivot = index - 1;
  index = array.length - 1;
  while (index > pivot && array[index].compareTo (array[pivot]) <= 0) {
   index--;
  }
  swap(array, pivot, index);
  reverse(array, pivot + 1, array.length - 1);
  return true;
 }
 private void swap(String[] array, int i, int j) {
  String tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
 }
 private void reverse (String[] array, int start, int end) {
  for (int i = start, j = end; i < j; i++, j--) {
   swap(array, i, j);
  }
 }

}



No comments:

Post a Comment