Какая коллекция Java считает перестановки равными?

Question

Я хочу создавать коллекции, которые могут содержать повторяющиеся значения, в определенном порядке.

Другими словами:

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

На самом деле, я хочу, чтобы иметь набор этих коллекций, так что если я пытаюсь добавить как { 1, 1, 2 } и { 2, 1, 1 }, второй .add() не делает ничего.

Есть ли стандартная коллекция, которая уже ведет себя таким образом?

Если я правильно понимаю:

• ArrayList позволяет дублирующие значения, но имеет фиксированный порядок
• HashSet позволяет для того, чтобы быть произвольным, но дубликат не дорожит
• TreeSet гарантирует, что заказ константа, но не допускает повторяющихся значений

Есть ли коллекция, которую я упустил, которая допускает как повторяющиеся значения, так и произвольные или фиксированные порядок, так что две коллекции с одинаковыми элементами считаются равными?

---

@asteri спросил о моем прецеденте. В игре у меня есть блоки разной длины, которые можно уложить от конца до конца, чтобы заполнить определенное расстояние. Например, если расстояние равно 10, оно может быть заполнено 2-3-5 или 5-2-3 или 3-3-4 или 3-4-3 или любое количество других перестановок. В зависимости от того, какие блоки доступны, я хочу составить список всех возможных коллекций, которые помогут заполнить пробел.

---

CUSTOM РЕШЕНИЕ
@sprinter предложил создать подкласс ArrayList. @dasblinkenlight и @Dici предложили использовать карту для хранения { Element : Count } записей. Я решил объединить эти два предложения. Ниже представлен подкласс TreeMap. Клавиши всегда сохраняются в том же порядке, чтобы гарантировать, что метод hashCode() производит одно и то же значение, например, с теми же ключами и значениями.

Я использовал метод increment, чтобы упростить добавление нового вхождения определенного целочисленного значения.

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

Answer 1

Я думаю, что ваш лучший вариант, чтобы обернуть Map таким образом:

• ключей являются вашими значениями
• значения числа вхождений ключей
• равного метода, основанным на Map.keySet() равенство, если число случаев имеет значение, Map.equals() в противном случае

Answer 2

В встроенных библиотеках Java нет ничего, но Guava Multiset делает это.

Answer 3

HashMap<Integer,Integer> мог бы представлять вашу коллекцию, если вы храните значение в качестве ключа и количество раз, которое это значение отображается в качестве значения на карте. Например, ваша коллекция {1, 1, 2} будет представлена ​​следующим образом:

{{ 1 : 2 }, { 2 : 1 }} 

означает, что есть два элемента с значением 1 (первая пара целых чисел), и один элемент с значением 2 (вторая пара целых чисел).

Answer 4

Этот тип коллекции обычно известен как multiset. В стандартную библиотеку не включены реализации мультимножеств, но внешние библиотеки Guava включают мультимножества.

Answer 5

Я хотел бы предложить создать подкласс ArrayList, который переопределяет метод Equals:

class MultiMemberList extends ArrayList { 
    public boolean equals(Object other) { 
     if (this == other) 
      return true; 
     if (!(other instanceof MultiMemberList)) 
      return false; 
     MultiMemberList otherList = (MultiMemberList)other; 
     if (size() != otherList.size()) 
      return false; 
     return stream().distinct().allMatch(element -> countElement(element) == otherList.countElement(element)); 
    } 

    private int countElement(Object element) { 
     return stream().filter(element::equals).count(); 
    } 
} 

Я не сделал это родовое, чтобы держать это простой, но очевидно, что вы должны сделать это.

Вы также должны переопределить хеш-функцию: простейшей задачей было бы отсортировать список перед вызовом хэша суперкласса.

После того, как вы осуществили это, установите, что добавленные объекты MultiMemberList будут работать так, как вы ожидаете: он не добавит второй список, который будет равен первому в соответствии с этим определением.

Answer 6

Вы можете использовать Bag от Eclipse Collections, также известный как Multiset.

MutableBag<Integer> bag1 = Bags.mutable.with(1, 1, 2); 
MutableBag<Integer> bag2 = Bags.mutable.with(1, 2, 1); 
Assert.assertEquals(bag1, bag2); 

Поскольку ваша коллекция будет содержать только ints, лучше использовать примитивный пакет. IntHashBag опирается на int[] массивы, а не Object[] массивы, использует меньше памяти и может быть быстрее.

MutableIntBag intBag1 = IntBags.mutable.with(1, 1, 2); 
MutableIntBag intBag2 = IntBags.mutable.with(1, 2, 1); 
Assert.assertEquals(intBag1, intBag2); 

Примечание: Я коммиттер для коллекций Eclipse.