How to permute an array of integers without generating mirrored permutations (Java)

Question

I have written a method to permute an array of integers in java. However I could not figure out how I can prevent finding mirrored permutations. For example I want all permutations of [1,2,3]. These would be:

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

The three last permutations are mirrored permutations, that I do not want to find at all. The reason for this is, that I am trying to implement a brute force solution for the traveling salesman problem. By discarding the mirrored permutations I could save some time, as it does not matter in which direction the tour is performed. The cost of the tour would be the same.

My idea was following: As seen in the example above, in the mirrored permutations the 2 is always in front of the 1. If I iterate through the array and find the 2 but not yet the 1, it means that the 1 is saved at a later index. Which means I can stop this permute. However I can not figure out how to perform this check. Moreover I do not know if this approach is the best way to solve this problem. How can I perform this check? Are there better approaches?

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

I have not defined anything for the mirrored permutation yet, because I do not know how. I am stuck at this point somehow. — Jul
– Jul, Commented May 15, 2019 at 19:25
Perhaps you mean two permutations that are the reversed image of each other? So 1234 and 4321 are "mirrored" ? — David Soroko
– David Soroko, Commented May 15, 2019 at 20:28
Yes, this is what I meant. I do not want this permutations to be printed out. And it would be cool, if it is possible to dismiss a swap if it gets clear that a permutation will be mirrored — Jul
– Jul, Commented May 15, 2019 at 20:32
For N elements, instead of N! permutations you will have (N!) / 2 which is insignificant for non trivial N. Still interested in this optimization? — David Soroko
– David Soroko, Commented May 15, 2019 at 20:57

imperezivan · Accepted Answer · 2019-05-15 20:46:50Z

You can create a DTO class 'Permutation' with a equals method to compare normal and reversed array and save each Permutation in a Set in this way reversed array will match as repeated and be omitted

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

Collectives™ on Stack Overflow

How to permute an array of integers without generating mirrored permutations (Java)

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related