Permutation of a list with equals objects - Java

Question
List<String> original = Lists.newArrayList("A", "B", "C");
Collection<List<String>> permutations= Collections2.orderedPermutations(original)

gives

[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]

Great, now I have all possible permutations. But let's say A and C are equal, their order does not matter when they are next to each other.

Wanted result:

[A, C, B] or [C, A, B]
[B, A, C] or [B, C, A]    
[A, B, C]
[C, B, A]

So we tried using a Comparator

    Collection<List<String>> permutations= Collections2.orderedPermutations(original, new Comparator<String>() {
        @Override
        public int compare(final String o1, final String o2) {
            if ((o1.equals("A") && o2.equals("C")) || (o2.equals("A") && o1.equals("C"))) {
                return 0;
            }
            return o1.compareTo(o2);
        }
    });

But this gave us not the result we expected

[A, B, C]
[A, C, B]

Any suggestions how to get the wanted result? Although we used guava, any lib or custom solution is ok.


Show source
| java   | permutation   2016-12-28 11:12 3 Answers

Answers ( 3 )

  1. 2016-12-28 11:12

    I would expect this to work. I have not tested.

        public int compare(String o1, String o2) {
            if (o1.equals("C")) o1 = "A";
            if (o2.equals("C")) o2 = "A";
            return o1.compareTo(o2);
        }
    

    Edit: added missing parenthesis

  2. 2016-12-28 11:12

    If you want to remove permutations that are logically equivalent, then I think you should start by writing out the actual 3-permutations as they would really appear if A and C were the same thing:

    [A, B, A]
    [A, A, B]
    [B, A, A]
    [B, A, A]
    [A, A, B]
    [A, B, A]
    

    With duplicates removed, you would be left with this:

    [A, B, A]
    [A, A, B]
    [B, A, A]
    

    By using a Set<List<String>> you can keep the duplicates out, i.e.

    List<String> original = Lists.newArrayList("A", "B", "C");
    Collection<List<String>> permutations = Collections2.orderedPermutations(original);
    
    // now add your collection to a set to remove duplicates
    Set<List<String>> permsNoDupes = new HashSet<>(permutations);
    
  3. 2016-12-28 13:12

    My suggestion is in pair of ("A", "C") & ("C", "A") always put "A" first and transform it to ("A", "C")

        List<String> original = Lists.newArrayList("A", "B", "C");
        Set<List<String>> permutations = Collections2.orderedPermutations(original).
                stream().
                map(list -> {
                    int indexOfc = list.get(0) == "C" ? 0 : (list.get(1) == "C" ? 1 : -1);
                    if (indexOfc != -1 && list.get(indexOfc + 1) == "A") {
                        // modifications not allowed on original list
                        list = new ArrayList<>(list); 
                        list.set(indexOfc, "A");
                        list.set(indexOfc + 1, "C");
                    }
                    return list;
                }).collect(Collectors.toSet());
    

    Results are

    [[A, B, C], [C, B, A], [B, A, C], [A, C, B]]
    
◀ Go back