Skip to content

Instantly share code, notes, and snippets.

@kjkrol
Created September 3, 2015 19:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save kjkrol/9c4199081eb2d5db7a99 to your computer and use it in GitHub Desktop.
Save kjkrol/9c4199081eb2d5db7a99 to your computer and use it in GitHub Desktop.
Permutation algorithm for array of integers in Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
/**
* @author Karol Krol
*/
public class Permutation {
private Permutation() {
}
public static List<List<Integer>> permutation(final int[] numbers) {
final PermutationCollector permutationCollector = new PermutationCollector();
permutation(new int[0], numbers, permutationCollector);
return permutationCollector.getResult();
}
private static void permutation(int[] prefix, int[] array, final Consumer<int[]> operation) {
int length = array.length;
if (length == 0) {
operation.accept(prefix);
} else {
for (int i = 0; i < length; ++i) {
final int[] newPrefix = append(prefix, array[i]);
final int[] reducedArray = reduce(array, i);
permutation(newPrefix, reducedArray, operation);
}
}
}
private static int[] append(int[] array, int element) {
int newLength = array.length + 1;
array = Arrays.copyOf(array, newLength);
array[newLength - 1] = element;
return array;
}
private static int[] reduce(int[] array, int index) {
final int newLength = array.length - 1;
if (index == 0) {
return Arrays.copyOfRange(array, 1, array.length);
} else {
final int[] dest = new int[newLength];
System.arraycopy(array, 0, dest, 0, index);
System.arraycopy(array, index + 1, dest, index, newLength - index);
return dest;
}
}
public static class PermutationCollector implements Consumer<int[]> {
private List<List<Integer>> result = new ArrayList<>();
@Override
public void accept(int[] ints) {
result.add(IntStream.of(ints).boxed().collect(Collectors.toList()));
}
public List<List<Integer>> getResult() {
return result;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment