Permutations.java

packagecom.jwetherell.algorithms.mathematics;

importjava.util.LinkedList;
importjava.util.List;

/**
 * In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence 
 * or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Permutation">Permutation (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 * @author Lucjan Roslanowski <lucjanroslanowski@gmail.com>
 */
publicclassPermutations { 

privatePermutations() { }

/** 
 * N! permutation of the characters in the string (in order)
 */
publicstaticString[] permutations(StringstringToGeneratePermutationsFrom) {
finalintsize = numberOfPermutations(stringToGeneratePermutationsFrom.length());
finalString[] list = newString[size];
finalchar[] prefix = newchar[0];
finalchar[] chars = stringToGeneratePermutationsFrom.toCharArray();
permutations(list, 0, prefix, chars, 0, chars.length);
returnlist;
 }

privatestaticfinalintnumberOfPermutations(intN) {
// factorial
intresult = N;
while (N > 1)
result *= --N;
returnresult;
 }

privatestaticfinalintpermutations(String[] list, intindex, char[] prefix, char[] remaining, intprefixLength, intremainingLength) {
finalintN = remainingLength-prefixLength;
if (N == 0) {
list[index]=newString(prefix);
index++;
 } else {
for (inti=0; i<N; i++) {
finalchar[] prefChars = newchar[prefixLength+1];
System.arraycopy(prefix, 0, prefChars, 0, prefixLength);
System.arraycopy(remaining, i, prefChars, prefixLength, 1);

finalchar[] restChars = newchar[N-1];
System.arraycopy(remaining, 0, restChars, 0, i);
System.arraycopy(remaining, i+1, restChars, i, N-(i+1));

index = permutations(list, index, prefChars, restChars, remainingLength-(N-1), remainingLength);
 }
 }
returnindex;
 }

/**
 * Permutations of numbers in an array using recursion
 * <br>
 * int numbers[] = {7,5,3};
 * LinkedList<LinkedList<Integer>> result = getAllPermutations(numbers);
 */
publicstaticfinal <NextendsNumber> List<List<N>> getAllPermutations(finalN[] numbers){
finalList<List<N>> result = newLinkedList<List<N>>();
returngetAllPermutations(numbers, result);
 }

privatestaticfinal <NextendsNumber> List<List<N>> getAllPermutations(finalN[] numbers, List<List<N>> result){
//numbers given in an array are also a permutation
LinkedList<N> firstPermutation = newLinkedList<N>();
for (Nel : numbers)
firstPermutation.add(el);
result.add(firstPermutation);
//let's permute all elements in array starting from index 0
returnpermute(numbers, 0, result);
 }

privatestaticfinal <NextendsNumber> List<List<N>> permute(finalN[] numbers, intcurrentElementIndex, List<List<N>> result){
if(currentElementIndex == numbers.length - 1)
returnresult;

for(inti = currentElementIndex; i < numbers.length; ++i){
//swapping two elements
Ntemp = numbers[i];
numbers[i] = numbers[currentElementIndex];
numbers[currentElementIndex] = temp;

permute(numbers, currentElementIndex + 1,result);

//all next permutation found
if(i != currentElementIndex){
LinkedList<N> nextPermutation = newLinkedList<N>();
for(intj = 0; j < numbers.length; j++)
nextPermutation.add(numbers[j]);
result.add(nextPermutation);
 }

//swapping back two elements 
temp = numbers[i];
numbers[i] = numbers[currentElementIndex];
numbers[currentElementIndex] = temp;
 } 
returnresult;
 }
}