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 ArrayListgeneratePermutation (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