如何在不生成镜像排列(Java)的情况下排列整数数组

Question

我已经写了一种方法，将整数数组置于Java中。但是，我无法弄清楚如何阻止查找镜像排列。例如，我想要[1,2,3]的所有排列。这些是：

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

最后三个排列是镜像排列，我根本不想找到。这样做的原因是，我试图为旅行推销员问题实施蛮力解决方案。通过丢弃镜像排列，我可以节省一些时间，因为在执行巡回演出的哪个方向上无关紧要。巡回演出的费用将相同。

我的想法如下：如上所述，在镜像排列中，2总是在1的前面。如果我迭代阵列并找到2但尚未找到1保存在以后的索引中。这意味着我可以停止此输入。但是，我无法弄清楚如何执行此检查。而且，我不知道这种方法是否是解决此问题的最佳方法。我该如何执行此支票？有更好的方法吗？

public void bruteforce(Graph g) {
    int[] elements = new int[g.size()];
    int length = g.size();
    for(int i = 0; i < elements.length; i++) {
        elements[i] = i;
    }
    permute(elements, length);
}
public void permute(int[] elements, int length) {
    if(length == 1) {
        for(int i = 0; i < length; i++) {
            System.out.println(Arrays.toString(elements));
        }
    }else {
        for(int i = 1; i < length; i++) {
            permute(elements, length-1);
            if(length % 2 == 1) {
                swap(elements, 1, length-1);
            }else {
                swap(elements, i, length-1);
            }
        }
    }
}
public void swap(int[] elements, int firstElement, int secondElement) {
    int tmp = elements[firstElement];
    elements[firstElement] = elements[secondElement];
    elements[secondElement] = tmp;
}

Answer 1

您可以使用平等方法创建DTO类'置换式'并以这种方式将每个排列保存在Set中

 ...
 Set<Permutation> permutations = new HashSet<>();
 public void permute(int[] elements, int length) {
    if(length == 1) {
        for(int i = 0; i < length; i++) {
            permutations.add(new Permutation(elements));
         }
...
public class Permutation {
    private Integer[] elements;
    public Permutation(Integer... elements) {
    this.elements = elements;
    }
    @Override
    public int hashCode() {
    return elements.length;
    }
    @Override
    public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj == null) {
        return false;
    }
    if (getClass() != obj.getClass()) {
        return false;
    }
    Permutation other = (Permutation) obj;
    // reversed elements
    List<Integer> revCurElements = Arrays.asList(this.elements);
    Collections.reverse(revCurElements);
    if (Arrays.equals(this.elements, other.elements) || Arrays.equals(revCurElements.toArray(new Integer[1]), other.elements)) {
        return true;
    }
    return false;
    }
}