CODEWITHSUNDEEP
javaarrays
Marius Kuzm
Marius Kuzm

Reputation: 159

Array permutation with no "duplicate" solutions

A route is described as [1,2,3,4]. For the route [1,2,3,4] a duplicate solution would be [4,3,2,1]. I am able to print all permutations of the array, but how would I extract the "unique" routes.

permute(java.util.Arrays.asList(1,2,3,4), 0);

static void permute(java.util.List<Integer> arr, int k){
    for(int i = k; i < arr.size(); i++){
        java.util.Collections.swap(arr, i, k);
        permute(arr, k+1);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() -1){
        System.out.println(java.util.Arrays.toString(arr.toArray()));
    }
}

Upvotes: 1

Views: 398

Answers (2)

Thomas
Thomas

Reputation: 88707

Well I'd say such a "path" could be described as a list of "hops" i.e. a tuple of adjacent points. Thus 1,2,3,4 could become [1,2],[2,3],[3,4]. Now if you build the tuples using the smaller value first 4,3,2,1 would become [3,4],[2,3],[2,1] - as you can see that would be the same tuples as for 1,2,3,4. Thus a permutation would be equal to another if it has the same tuples in any order (i.e. a set of tuples).

Using that you could build a Map<Set<Tuple>, List<ArrayList<Integer>>> to get all paths that have the same "hops". Just note that map keys should be immutable so it would be best to either use a true immutable set implementation or at least decorate it with Collections.unmodifiableSet().

Here's a possible Tuple class you could use: 

class Tuple {
    private int l,r;

    public Tuple( int a, int b ) {
      if ( a > b ) {
        l = b;
        r = a;
      } else {
        l = a;
        r = b;
      }
    }

    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + l;
      result = prime * result + r;
      return result;
    }

    @Override
    public boolean equals( Object obj ) {
      if( this == obj ) return true;
      if( obj == null ) return false;
      if( getClass() != obj.getClass() ) return false;
      Tuple other = (Tuple) obj;
      if( l != other.l ) return false;
      if( r != other.r ) return false;
      return true;
    }

    @Override
    public String toString() {
      return "[" + l + ", " + r + "]";
    }       
  }

Then pass the Map<Set<Tuple>, List<List<Integer>>> to permute(...) and fill it: 

static void permute(List<Integer> arr, int k, Map<Set<Tuple>, List<List<Integer>>> results){
  for(int i = k; i < arr.size(); i++){
      Collections.swap(arr, i, k);
      permute(arr, k+1, results);
      Collections.swap(arr, k, i);
  }
  if (k == arr.size() -1){
    Set<Tuple> path = new HashSet<>();
    for( int i = 0; i < arr.size() - 1; i++ ) {
      path.add( new Tuple(arr.get( i ), arr.get( i + 1 )) );
    }

    results.computeIfAbsent( Collections.unmodifiableSet( path ), v -> new ArrayList<List<Integer>>() ).add( new ArrayList<>( arr ) );
  }
}

Using the map you could then get all the permutations that share the same "hops". In your case where there's basically one straight path from start to end or back there will be only 2 equal permutations.

Upvotes: 0

Gabistic
Gabistic

Reputation: 53

If you mean [1,2,3,4]=[4,3,2,1]=[1,3,2,4]=...,

1) transform each permutation in ArrayList

2) Sort each permutation by their natural sort order

3) Add all permutations sorted in a Set

Upvotes: 1

Related Questions