Jaka kolekcja Java uważa permutacje za równe?

Question

Chcę utworzyć kolekcje, które mogą zawierać zduplikowane wartości, w dowolnej kolejności.

Innymi słowy:

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

W rzeczywistości, chcę mieć zestaw tych zbiorów, więc jeśli próbuję dodać zarówno { 1, 1, 2 } i { 2, 1, 1 }, drugi .add() nie będzie właściwie nic.

Czy istnieje standardowa kolekcja, która już działa w ten sposób?

Jeśli dobrze rozumiem:

• ArrayList pozwala na zduplikowane wartości, ale ma ustalony porządek
• HashSet pozwala na celu być dowolna, ale nie zduplikowane wartości
• TreeSet zapewnia, że ​​zamówienie jest stała, ale nie pozwala na powielanie wartości

Czy istnieje kolekcja, którą pominąłem, która pozwala na kopiowanie zarówno wartości dowolnych, jak i stałych kolejności, tak aby dwie kolekcje z tymi samymi elementami były uważane za równe?

---

@asteri pytanie o mój przypadek użycia. W grze mam klocki o różnych długościach, które można ułożyć do końca, aby wypełnić pewną odległość. Na przykład, jeśli odległość wynosi 10, można ją wypełnić 2-3-5 lub 5-2-3 lub 3-3-4 lub 3-4-3 lub dowolną liczbą innych permutacji. W zależności od tego, jakie bloki są dostępne, chcę utworzyć listę wszystkich możliwych kolekcji, które rozwiążą lukę.

---

niestandardowe rozwiązania
@sprinter zaproponował utworzenie podklasy ArrayList. @dasblinkenlight i @Dici zasugerowali użycie Map do przechowywania wpisów { Element : Count }. Postanowiłem połączyć te dwie sugestie. Poniżej znajduje się podklasa TreeMap. Klucze są zawsze przechowywane w tej samej kolejności, aby zapewnić, że metoda hashCode() generuje taką samą wartość dla tych samych kluczy i wartości.

Użyłem metody increment, aby ułatwić dodanie nowego wystąpienia konkretnej liczby całkowitej "wartość".

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

Myślę, że lepszym rozwiązaniem jest, aby zawinąć Map ten sposób:

• klawisze są twoje wartości
• wartościami są liczby wystąpień kluczy
• równa metoda oparta na Map.keySet() równość, jeśli liczba wystąpień ma znaczenie, Map.equals() inaczej

Answer 2

W bibliotekach wbudowanych w Javie nie ma nic, ale Guna Multiset to robi.

Answer 3

HashMap<Integer,Integer> byłby w stanie reprezentować Twoją kolekcję, jeśli przechowujesz wartość jako klucz i liczbę razy, gdy ta wartość pojawia się jako wartość na mapie. Na przykład, kolekcja {1, 1, 2} byłby reprezentowany tak:

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

co oznacza, że ​​istnieją dwa elementy o wartości 1 (pierwsza para liczb całkowitych) oraz jeden przedmiot o wartości 2 (druga para liczby całkowite).

Answer 4

Ten typ kolekcji jest powszechnie znany jako wielociętowy . Nie ma implementacji multisetów zawartych w standardowej bibliotece, ale zewnętrzne biblioteki Guava zawierają multisety.

Answer 5

Proponuję utworzenie podklasy ArrayList, który zastępuje metodę wynosi:

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

Nie zrobiłem tego generic zachować to proste, ale oczywiście należy zrobić.

Należy również zastąpić funkcję skrótu: najprostszą rzeczą do zrobienia byłoby sortowanie listy przed wywołaniem skrótu super klasy.

Po zaimplementowaniu tej opcji zestaw z dodanymi obiektami MultiMemberList będzie działał zgodnie z oczekiwaniami: nie doda drugiej listy, która będzie równa pierwszej zgodnie z tą definicją.

Answer 6

Można użyć Bag z Eclipse Collections, znanego również jako Multiset.

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

Ponieważ twoja kolekcja będzie zawierała tylko ints, lepiej użyć prymitywnej torby. IntHashBag jest wspierany przez tablice int[], a nie tablice Object[], zużywa mniej pamięci i może być szybszy.

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

Uwaga: Jestem committer dla zbiorów Eclipse.