我已經編寫了一種方法來置換 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，則意味著 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;}
1 回答
冉冉說
TA貢獻1877條經驗 獲得超1個贊
您可以使用 equals 方法創建一個 DTO 類“Permutation”來比較正常數組和反向數組，并將每個 Permutation 保存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;
}
}
添加回答
舉報
0/150
提交
取消