Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What Java collection considers permutations to be equal?

I want to create collections which may contain duplicate values, in no particular order.

In other words:

{ 1, 1, 2 } == { 2, 1, 1 } == { 1, 2, 1 }

In fact, I want to have a Set of these collections, so if I try to add both { 1, 1, 2 } and { 2, 1, 1 }, the second .add() will not actually do anything.

Is there a standard collection that already behaves this way?

If I understand correctly:

  • ArrayList allows for duplicate values, but has a fixed order
  • HashSet allows for the order to be arbitrary but no duplicate values
  • TreeSet ensures that the order is constant, but allows no duplicate values

Is there a collection that I have overlooked that allows for both duplicate values and either an arbitrary or a fixed order, so that two collections with the same elements are consider equal?


@asteri asked about my use case. In a game, I have blocks of different lengths which can be laid end to end to fill a certain distance. For example, if the distance is 10, it can be filled with 2-3-5 or 5-2-3 or 3-3-4 or 3-4-3, or any number of other permutations. Depending on what blocks are available, I want to make a list of all the possible collections that would solve fill the gap.


CUSTOM SOLUTION
@sprinter suggested creating a subclass of ArrayList. @dasblinkenlight and @Dici suggested using a Map to store { Element : Count } entries. I have chosen to combine these two suggestions. Below is a subclass of TreeMap. The keys are always stored in the same order, to ensure that the hashCode() method produces the same value for instance with the same keys and values.

I've used an increment method to make it easy to add a new occurrence of a particular integer "value".

package com.example.treematch;

import java.util.Map;
import java.util.TreeMap;

public class TreeMatch<K> extends TreeMap<K, Integer> {

  @Override
  public boolean equals(Object other) {
    if (this == other) {
      return true;
    }

    if (!(other instanceof TreeMatch)) {
      return false;
    }

    TreeMatch otherMatch = (TreeMatch) other;
    if (size() != otherMatch.size()) {
      return false;
    }

    for (Object key : this.keySet()) {
        if (!otherMatch.containsKey(key)) {
            return false;
        }
    }

    for (Object key : otherMatch.keySet()) {
      if (!this.containsKey(key)) {
        return false;
      }

      if (this.get(key) != otherMatch.get(key)) {
        return false;
      }
    }

    return true;
  }

  public void increment(K key) {
    Integer value;

    if (this.containsKey(key)) {
      value = (this.get(key)) + 1;
    } else {
      value = 1;
    }

    this.put(key, value);
  }


  @Override
  public int hashCode() {
    int hashCode = 0;

    for (Map.Entry entry : this.entrySet()) {
      hashCode += entry.getKey().hashCode();
      hashCode = hashCode << 1;
      hashCode += entry.getValue().hashCode();
      hashCode = hashCode << 1;
    }

    return hashCode;
  }
}
like image 346
James Newton Avatar asked Jan 08 '15 01:01

James Newton


1 Answers

There's nothing in the Java built-in libraries, but Guava's Multiset does this.

like image 73
Louis Wasserman Avatar answered Nov 11 '22 00:11

Louis Wasserman