Как переставить массив целых чисел без генерации зеркальных перестановок (Java) - PullRequest
Новая
       20

Как переставить массив целых чисел без генерации зеркальных перестановок (Java)

2 голосов
/ 15 мая 2019

Я написал метод для перестановки массива целых чисел в 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 Ответ

1 голос
/ 15 мая 2019

Вы можете создать класс DTO 'Перестановка' с помощью метода equals, чтобы сравнить нормальный и обращенный массив и сохранить каждую Перестановку в 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;
    }

}
...