son - lista de enteros en java

Java ArrayList: ¿cómo puedo saber si dos listas son iguales, el orden no importa?

Question

Tengo dos ArrayLists de tipo Answer (clase hecha a sí misma).

Me gustaría comparar las dos listas para ver si contienen los mismos contenidos, pero sin importar el orden.

Ejemplo:

//These should be equal.
ArrayList<String> listA = {"a", "b", "c"}
ArrayList<String> listB = {"b", "c", "a"}

List.equals establece que dos listas son iguales si contienen el mismo tamaño, contenido y orden de elementos. Quiero lo mismo, pero sin importar el orden.

¿Hay una manera simple de hacer esto? ¿O tendré que hacer un ciclo for anidado y verificar manualmente cada índice de ambas listas?

Nota: No puedo cambiarlos de ArrayList a otro tipo de lista, deben permanecer así.

Answer 1

Convertir las listas a Guava''s Multiset funciona muy bien. Se comparan independientemente de su orden y también se tienen en cuenta los elementos duplicados.

static <T> boolean equalsIgnoreOrder(List<T> a, List<T> b) {
    return ImmutableMultiset.copyOf(a).equals(ImmutableMultiset.copyOf(b));
}

assert equalsIgnoreOrder(ImmutableList.of(3, 1, 2), ImmutableList.of(2, 1, 3));
assert !equalsIgnoreOrder(ImmutableList.of(1), ImmutableList.of(1, 1));

Answer 2

En ese caso, las listas {"a", "b"} y {"b", "a"} son iguales. Y {"a", "b"} y {"b", "a", "c"} no son iguales. Si usa una lista de objetos complejos, recuerde anular el método de iguales , ya que containsAll lo usa dentro.

if (oneList.size() == secondList.size() && oneList.containsAll(secondList)){
        areEqual = true;
}

Answer 3

Es una forma alternativa de verificar la igualdad de las listas de matrices que pueden contener valores nulos:

List listA = Arrays.asList(null, "b", "c");
List listB = Arrays.asList("b", "c", null);

System.out.println(checkEquality(listA, listB)); // will return TRUE


private List<String> getSortedArrayList(List<String> arrayList)
{
    String[] array = arrayList.toArray(new String[arrayList.size()]);

    Arrays.sort(array, new Comparator<String>()
    {
        @Override
        public int compare(String o1, String o2)
        {
            if (o1 == null && o2 == null)
            {
                return 0;
            }
            if (o1 == null)
            {
                return 1;
            }
            if (o2 == null)
            {
                return -1;
            }
            return o1.compareTo(o2);
        }
    });

    return new ArrayList(Arrays.asList(array));
}

private Boolean checkEquality(List<String> listA, List<String> listB)
{
    listA = getSortedArrayList(listA);
    listB = getSortedArrayList(listB);

    String[] arrayA = listA.toArray(new String[listA.size()]);
    String[] arrayB = listB.toArray(new String[listB.size()]);

    return Arrays.deepEquals(arrayA, arrayB);
}

Answer 4

Esto se basa en la solución @cHao. Incluí varias correcciones y mejoras de rendimiento. Esto funciona aproximadamente dos veces más rápido que la solución equals-ordered-copy. Funciona para cualquier tipo de colección. Las colecciones vacías y nulas se consideran iguales. Use para su ventaja;)

/**
 * Returns if both {@link Collection Collections} contains the same elements, in the same quantities, regardless of order and collection type.
 * <p>
 * Empty collections and {@code null} are regarded as equal.
 */
public static <T> boolean haveSameElements(Collection<T> col1, Collection<T> col2) {
    if (col1 == col2)
        return true;

    // If either list is null, return whether the other is empty
    if (col1 == null)
        return col2.isEmpty();
    if (col2 == null)
        return col1.isEmpty();

    // If lengths are not equal, they can''t possibly match
    if (col1.size() != col2.size())
        return false;

    // Helper class, so we don''t have to do a whole lot of autoboxing
    class Count
    {
        // Initialize as 1, as we would increment it anyway
        public int count = 1;
    }

    final Map<T, Count> counts = new HashMap<>();

    // Count the items in list1
    for (final T item : col1) {
        final Count count = counts.get(item);
        if (count != null)
            count.count++;
        else
            // If the map doesn''t contain the item, put a new count
            counts.put(item, new Count());
    }

    // Subtract the count of items in list2
    for (final T item : col2) {
        final Count count = counts.get(item);
        // If the map doesn''t contain the item, or the count is already reduced to 0, the lists are unequal 
        if (count == null || count.count == 0)
            return false;
        count.count--;
    }

    // If any count is nonzero at this point, then the two lists don''t match
    for (final Count count : counts.values())
        if (count.count != 0)
            return false;

    return true;
}

Answer 5

Lo mejor de ambos mundos [@DiddiZ, @Chalkos]: este se basa principalmente en el método @Chalkos, pero corrige un error (ifst.next ()) y mejora los controles iniciales (tomados de @DiddiZ) y elimina la necesidad de copie la primera colección (simplemente elimina elementos de una copia de la segunda colección).

Al no requerir una función de hashing o clasificación, y permitir una existencia temprana en la falta de igualdad, esta es la implementación más eficiente hasta el momento. Eso es a menos que tenga una longitud de recopilación de miles o más, y una función de hashing muy simple.

public static <T> boolean isCollectionMatch(Collection<T> one, Collection<T> two) {
    if (one == two)
        return true;

    // If either list is null, return whether the other is empty
    if (one == null)
        return two.isEmpty();
    if (two == null)
        return one.isEmpty();

    // If lengths are not equal, they can''t possibly match
    if (one.size() != two.size())
        return false;

    // copy the second list, so it can be modified
    final List<T> ctwo = new ArrayList<>(two);

    for (T itm : one) {
        Iterator<T> it = ctwo.iterator();
        boolean gotEq = false;
        while (it.hasNext()) {
            if (itm.equals(it.next())) {
                it.remove();
                gotEq = true;
                break;
            }
        }
        if (!gotEq) return false;
    }
    // All elements in one were found in two, and they''re the same size.
    return true;
}

Answer 6

Piensa cómo lo harías tú mismo, sin una computadora o un lenguaje de programación. Te doy dos listas de elementos, y tienes que decirme si contienen los mismos elementos. ¿Como lo harias?

Un enfoque, como se mencionó anteriormente, es ordenar las listas y luego ir elemento por elemento para ver si son iguales (que es lo que hace List.equals ). Esto significa que puede modificar las listas o puede copiarlas, y sin conocer la asignación, no puedo saber si se permiten ambas o ambas cosas.

Otro enfoque sería revisar cada lista, contando cuántas veces aparece cada elemento. Si ambas listas tienen los mismos recuentos al final, tienen los mismos elementos. El código para eso sería traducir cada lista a un mapa de elem -> (# of times the elem appears in the list) y luego llamar a equals en los dos mapas. Si los mapas son HashMap , cada una de esas traducciones es una operación O (N), como lo es la comparación. Eso te dará un algoritmo bastante eficiente en términos de tiempo, a costa de algo de memoria adicional.

Answer 7

Probablemente la forma más fácil para cualquier lista sería:

listA.containsAll(listB) && listB.containsAll(listA)

Answer 8

Puede ordenar ambas listas usando Collections.sort() y luego usar el método equals. Una solución un poco mejor es comprobar primero si son de la misma longitud antes de ordenar, si no lo son, entonces no son iguales, luego ordenar, luego usar iguales. Por ejemplo, si tuviera dos listas de cadenas, sería algo así como:

public  boolean equalLists(List<String> one, List<String> two){     
    if (one == null && two == null){
        return true;
    }

    if((one == null && two != null) 
      || one != null && two == null
      || one.size() != two.size()){
        return false;
    }

    //to avoid messing the order of the lists we will use a copy
    //as noted in comments by A. R. S.
    one = new ArrayList<String>(one); 
    two = new ArrayList<String>(two);   

    Collections.sort(one);
    Collections.sort(two);      
    return one.equals(two);
}

Answer 9

Si la cardinalidad de los elementos no importa (es decir, los elementos repetidos se consideran como uno), entonces hay una forma de hacerlo sin tener que ordenar:

boolean result = new HashSet<>(listA).equals(new HashSet<>(listB));

Esto creará un Set de cada List , y luego usará el HashSet de HashSet equals que (por supuesto) ignora el orden.

Si la cardinalidad es importante, entonces debe limitarse a las instalaciones proporcionadas por List ; La respuesta de @jschoen sería más apropiada en ese caso.

Answer 10

Si no espera ordenar las colecciones y necesita el resultado de que ["A" "B" "C"] no es igual a ["B" "B" "A" "C"],

l1.containsAll(l2)&&l2.containsAll(l1)

no es suficiente, probablemente necesites verificar el tamaño:

    List<String> l1 =Arrays.asList("A","A","B","C");
    List<String> l2 =Arrays.asList("A","B","C");
    List<String> l3 =Arrays.asList("A","B","C");

    System.out.println(l1.containsAll(l2)&&l2.containsAll(l1));//cautions, this will be true
    System.out.println(isListEqualsWithoutOrder(l1,l2));//false as expected

    System.out.println(l3.containsAll(l2)&&l2.containsAll(l3));//true as expected
    System.out.println(isListEqualsWithoutOrder(l2,l3));//true as expected


    public static boolean isListEqualsWithoutOrder(List<String> l1, List<String> l2) {
        return l1.size()==l2.size() && l1.containsAll(l2)&&l2.containsAll(l1);
}

Answer 11

Si te importa el orden, simplemente usa el método igual:

list1.equals(list2)

Answer 12

Solución que aprovecha el método de resta CollectionUtils:

import static org.apache.commons.collections15.CollectionUtils.subtract;

public class CollectionUtils {
  static public <T> boolean equals(Collection<? extends T> a, Collection<? extends T> b) {
    if (a == null && b == null)
      return true;
    if (a == null || b == null || a.size() != b.size())
      return false;
    return subtract(a, b).size() == 0 && subtract(a, b).size() == 0;
  }
}

Answer 13

Tuve el mismo problema y se me ocurrió una solución diferente. Este también funciona cuando hay duplicados involucrados:

public static boolean equalsWithoutOrder(List<?> fst, List<?> snd){
  if(fst != null && snd != null){
    if(fst.size() == snd.size()){
      // create copied lists so the original list is not modified
      List<?> cfst = new ArrayList<Object>(fst);
      List<?> csnd = new ArrayList<Object>(snd);

      Iterator<?> ifst = cfst.iterator();
      boolean foundEqualObject;
      while( ifst.hasNext() ){
        Iterator<?> isnd = csnd.iterator();
        foundEqualObject = false;
        while( isnd.hasNext() ){
          if( ifst.next().equals(isnd.next()) ){
            ifst.remove();
            isnd.remove();
            foundEqualObject = true;
            break;
          }
        }

        if( !foundEqualObject ){
          // fail early
          break;
        }
      }
      if(cfst.isEmpty()){ //both temporary lists have the same size
        return true;
      }
    }
  }else if( fst == null && snd == null ){
    return true;
  }
  return false;
}

Ventajas en comparación con algunas otras soluciones:

• menos de O (N²) complejidad (aunque no he probado su rendimiento real en comparación con las soluciones en otras respuestas aquí);
• sale temprano;
• comprueba nulo;
• funciona incluso cuando hay duplicados: si tiene una matriz [1,2,3,3] y otra matriz [1,2,2,3] mayoría de las soluciones le dicen que son las mismas al no considerar el orden. Esta solución evita esto al eliminar elementos iguales de las listas temporales;
• usa igualdad semántica ( equals ) y no igualdad de referencia ( == );
• no ordena itens, por lo que no necesitan ser ordenables (mediante implement Comparable ) para que esta solución funcione.

Answer 14

Yo diría que estas respuestas pierden un truco.

Bloch, en su esencial, maravillosa y concisa Java efectiva , dice, en el ítem 47, título "Conozca y use las bibliotecas", "Para resumir, no reinvente la rueda". Y él da varias razones muy claras por las que no.

Aquí hay algunas respuestas que sugieren métodos de CollectionUtils en la biblioteca de colecciones de Apache Commons, pero ninguno ha detectado la forma más bella y elegante de responder a esta pregunta :

Collection<Object> culprits = CollectionUtils.disjunction( list1, list2 );
if( ! culprits.isEmpty() ){
  // ... then in most cases you will ardently wish to do something to these culprits: 
  // at the very least, name-and-shame them.

}

Culpables : es decir, los elementos que no son comunes a ambas Lists . Determinar qué culpables pertenecen a list1 y cuál a list2 es relativamente sencillo usando CollectionUtils.intersection( list1, culprits ) y CollectionUtils.intersection( list2, culprits ) .
Sin embargo, tiende a desmoronarse en casos como {"a", "a", "b"} disjunction con {"a", "b", "b"} ... excepto que esto no es un error del software, pero inherente a la naturaleza de las sutilezas / ambigüedades de la tarea deseada.

NB Al principio me decepcionó que ninguno de los métodos de CollectionUtils proporciona una versión sobrecargada que le permite imponer su propio Comparator (para que pueda redefinir equals para que se adapte a sus propósitos).

Pero desde collections4 4.0 hay una nueva clase, Equator que "determina la igualdad entre los objetos de tipo T". Al examinar el código fuente de collections4 CollectionUtils.java, parecen estar usando esto con algunos métodos, pero por lo que puedo ver, esto no es aplicable a los métodos en la parte superior del archivo, usando la clase CardinalityHelper ... que incluyen disjunction e intersection .

Supongo que la gente Apache aún no ha llegado a esto porque no es trivial: tendría que crear algo así como una clase "AbstractEquatingCollection", que en lugar de utilizar los elementos equals inherentes de los elementos y los métodos hashCode tendrían que utilice los de Equator para todos los métodos básicos, como add , contains , etc. NB, de hecho, cuando mira el código fuente, AbstractCollection no implementa add , ni sus subclases abstractas, como AbstractSet ... tiene que esperar hasta que se implementen las clases concretas como HashSet y ArrayList before add . Un gran dolor de cabeza

Mientras tanto, mira este espacio, supongo. La solución obvia provisional sería envolver todos sus elementos en una clase contenedora personalizada que use equals y hashCode para implementar el tipo de igualdad que desea ... luego manipule las Collections de estos objetos contenedoras.

Answer 15

Apache Commons Collections al rescate una vez más:

List<String> listA = Arrays.asList("a", "b", "b", "c");
List<String> listB = Arrays.asList("b", "c", "a", "b");
System.out.println(CollectionUtils.isEqualCollection(listA, listB)); // true

List<String> listC = Arrays.asList("a", "b", "c");
List<String> listD = Arrays.asList("a", "b", "c", "c");
System.out.println(CollectionUtils.isEqualCollection(listC, listD)); // false

Documentos:

org.apache.commons.collections4.CollectionUtils

public static boolean isEqualCollection(java.util.Collection a,
                                        java.util.Collection b)

Devuelve true si la Collection dada contiene exactamente los mismos elementos con exactamente las mismas cardinalidades.

Es decir, si la cardinalidad de e en a es igual a la cardinalidad de e en b , para cada elemento e en a o b .

Parámetros:

• a - la primera colección, no debe ser null
• b - la segunda colección, no debe ser null

Devuelve: true si las colecciones contienen los mismos elementos con las mismas cardinalidades.

Answer 16

// helper class, so we don''t have to do a whole lot of autoboxing
private static class Count {
    public int count = 0;
}

public boolean haveSameElements(final List<String> list1, final List<String> list2) {
    // (list1, list1) is always true
    if (list1 == list2) return true;

    // If either list is null, or the lengths are not equal, they can''t possibly match 
    if (list1 == null || list2 == null || list1.size() != list2.size())
        return false;

    // (switch the two checks above if (null, null) should return false)

    Map<String, Count> counts = new HashMap<>();

    // Count the items in list1
    for (String item : list1) {
        if (!counts.containsKey(item)) counts.put(item, new Count());
        counts.get(item).count += 1;
    }

    // Subtract the count of items in list2
    for (String item : list2) {
        // If the map doesn''t contain the item here, then this item wasn''t in list1
        if (!counts.containsKey(item)) return false;
        counts.get(item).count -= 1;
    }

    // If any count is nonzero at this point, then the two lists don''t match
    for (Map.Entry<String, Count> entry : counts.entrySet()) {
        if (entry.getValue().count != 0) return false;
    }

    return true;
}