java - 将整数排列的完整 ArrayLists 排序为决策树结构

Question

背景:我有一个 ArrayList<Integer> . Integer s 是一些订单对象的引用 ID。稍后，这个列表将告诉一个分支定界算法，哪个顺序首先计划到时间表中，哪个第二等等。 B&B 是一种基于树的算法，我想用作深度优先搜索。

因此，我需要列表的每个排列。我第一次尝试使用递归:

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

并获取 3 个订单的输出:

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

但是在深度优先搜索的情况下，我需要:

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

这样我的树节点将按预期访问:

那么我该如何对递归得到的 Lists 进行排序呢？进入那个结构？

Answer 1

我设法提出了一种算法，可以以正确的顺序从原始输入列表中获取排列。它不依赖于被排序的列表内容。

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