0

Background: I have an ArrayList<Integer>. The Integers are reference-IDs to some order objects. Later, this list will tell a branch-and-bound-algorithm, which order to plan first into the schedule, which second etc.. B&B is a tree based algorithm i want to use as depth-first search.

So, i need every permutation of the list. My first try used recursion:

private List<List<Integer>> permutations(List<Integer> input) {

    List<List<Integer>> permutations = new ArrayList<List<Integer>>();

    if (input.size() == 0) {
        permutations.add(new ArrayList<Integer>());
        return permutations;
    }

    Integer firstElement = input.remove(0);

    List<List<Integer>> recursiveReturn = permutations(input);
    for (List<Integer> li : recursiveReturn) {

        for (int index = 0; index <= li.size(); index++) {
            List<Integer> temp = new ArrayList<Integer>(li);
            temp.add(index, firstElement);
            permutations.add(temp);
        }

    }
    return permutations;
}

and gets output for 3 orders:

[1, 2, 3] 
[2, 1, 3] 
[2, 3, 1] 
[1, 3, 2] 
[3, 1, 2] 
[3, 2, 1]

But in case of depth-first search, i need:

[1, 2, 3]
[1, 3, 2]  
[2, 1, 3] 
[2, 3, 1] 
[3, 1, 2] 
[3, 2, 1]

so that my tree nodes will be visited as expected: enter image description here

So how can i sort my recursively gotten Lists into that structure?

2
  • Is input always sorted and if not do you want the resulting permutations sorted? Or do you want if input is 1, 3, 2 the ouput [1, 3, 2] [1, 2, 3] [3, 1, 2] [3, 2, 1] [2, 1, 3] [2, 3, 1]
    – PKuhn
    Sep 3, 2015 at 14:34
  • Input is not always sorted, the permutations should be sorted as described, yes. Sep 3, 2015 at 14:53

2 Answers 2

2

I managed to come up with an algorithm that gets the permutations from the original input list in the correct order. it does not rely on the list contents being ordered.

private List<List<Integer>> permutations(List<Integer> input)
{
    List<List<Integer>> permutations = new ArrayList<>();
    // if input's size is one, then there is only one permutation to return
    // wrap it as single entry inside permutations and return 
    if (input.size() == 1) {
        permutations.add(input);
        return permutations;
    }

    // if input's size is more than one, then we need to calc permutations
    // we iterate over the input, each time taking out one cell
    // the remaining cells become tree "under" this cell
    for (int i = 0; i < input.size(); i++) {
        List<Integer> remainingCells = new ArrayList<>(input);
        Integer firstElement = remainingCells.remove(i);
        List<List<Integer>> permutationsUnderFirstElement = permutations(remainingCells);
        for (List<Integer> permutation : permutationsUnderFirstElement) {
            permutation.add(0, firstElement);
            permutations.add(permutation);
        }
    }
    return permutations;
}
0
1

How to sort existed permutations:

final List<List<Integer>> permutations = new ArrayList<>();
permutations.add(Arrays.asList(1, 2, 3));
permutations.add(Arrays.asList(1, 3, 2));
permutations.add(Arrays.asList(2, 1, 3));
permutations.add(Arrays.asList(2, 3, 1));
permutations.add(Arrays.asList(3, 1, 2));
permutations.add(Arrays.asList(3, 2, 1));

System.out.println("initial state=" + permutations);

Collections.reverse(permutations);

System.out.println("after shuffle=" + permutations);

final List<List<Integer>> result = permutations.stream().sorted((o1, o2) -> {
    final int length = o1.size();
    int diff = 0;
    for (int i = 0; i < length; ++i) {
        diff = o1.get(i) - o2.get(i);
        if (diff != 0) {
            break;
        }
    }
    return diff;
}).collect(Collectors.toList());

System.out.println("sorted again =" + result);

How to generate sorted permutations (gist):

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;
        }
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.