我已經(jīng)編寫了一種方法來(lái)置換 java 中的整數(shù)數(shù)組。但是我不知道如何防止找到鏡像排列。例如，我想要 [1,2,3] 的所有排列。這些將是：[1,2,3][1,3,2][3,1,2][3,2,1][2,3,1][2,1,3]最后三個(gè)排列是鏡像排列，我根本不想找到。這樣做的原因是，我正在嘗試為旅行商問題實(shí)施蠻力解決方案。通過丟棄鏡像排列，我可以節(jié)省一些時(shí)間，因?yàn)樵谀膫€(gè)方向執(zhí)行巡視并不重要。這次旅行的費(fèi)用是一樣的。我的想法如下：如上例所示，在鏡像排列中，2 始終在 1 之前。如果我遍歷數(shù)組并找到 2 但還沒有找到 1，則意味著 1 保存在一個(gè)后來(lái)的索引。這意味著我可以停止這種排列。但是我不知道如何執(zhí)行此檢查。此外，我不知道這種方法是否是解決此問題的最佳方法。我如何執(zhí)行此檢查？有更好的方法嗎？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 回答
冉冉說(shuō)
TA貢獻(xiàn)1877條經(jīng)驗(yàn) 獲得超1個(gè)贊
您可以使用 equals 方法創(chuàng)建一個(gè) DTO 類“Permutation”來(lái)比較正常數(shù)組和反向數(shù)組，并將每個(gè) Permutation 保存Set在這樣的反向數(shù)組中，這樣反向數(shù)組將匹配為重復(fù)并被省略
...
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;
}
}
添加回答
舉報(bào)
0/150
提交
取消