Created
September 3, 2015 19:31
-
-
Save kjkrol/9c4199081eb2d5db7a99 to your computer and use it in GitHub Desktop.
Permutation algorithm for array of integers in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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