Mantener una ArrayList de matrices únicas en java

Question

¿Cómo puedo mantener una ArrayList de matrices únicas?

Por ejemplo, si tengo las siguientes matrices:

int [] a = {1,2,3};
int [] b = {2,1,3};
int [] c = {2,1,3};

Según mi lógica, estoy considerando combinaciones únicas. Entonces, en el caso anterior a = b = c porque todos contienen "1" , "2" , "3" .

Idealmente, me pregunto si hay una estructura de datos en Java que reconozca esto.

Intenté lo siguiente:

Set<int []> result = new LinkedHashSet<>();
int [] x = {1,2,3};
int [] z = {2,1,3};
int [] m = {2,1,3};

result.add(x);
result.add(z);
result.add(m);

for(int [] arr: result){
    printArray(arr);
}

Mi salida fue:

1 2 3
2 1 3
2 1 3

Idealmente, me gustaría que mi salida solo imprima una de las combinaciones anteriores.

Answer 1

Definitivamente se siente extraño e incorrecto, pero podría usar un TreeSet con un Comparator personalizado. Dependiendo de sus necesidades, esto podría funcionar, pero al menos tenga en cuenta que esto está rompiendo el contrato general de la interfaz Set .

class Demo {
    public static void main(String[] args) throws Exception {
        Set<int[]> result = new TreeSet<>(new Hack());
        int[] x = {1,2,3};
        int[] z = {2,1,3};
        int[] m = {2,1,3};

        result.add(x);
        result.add(z);
        result.add(m);

        for (int[] arr : result) {
            System.out.println(Arrays.toString(arr));
        }
    }
}

class Hack implements Comparator<int[]> {

    @Override
    public int compare(int[] e1, int[] e2) {
        int[] copy1 = Arrays.copyOf(e1, e1.length);
        int[] copy2 = Arrays.copyOf(e2, e2.length);
        Arrays.sort(copy1);
        Arrays.sort(copy2);
        return Arrays.compare(copy1, copy2);
    }
}

Salida:

[1, 2, 3]

Si todavía está en Java 8, use esta implementación de Hack :

class Hack implements Comparator<int[]> {

    @Override
    public int compare(int[] e1, int[] e2) {
        int[] copy1 = Arrays.copyOf(e1, e1.length);
        int[] copy2 = Arrays.copyOf(e2, e2.length);
        Arrays.sort(copy1);
        Arrays.sort(copy2);
        int cmp = Integer.compare(copy1.length, copy2.length);
        if (cmp != 0) {
            return cmp;
        }
        for (int i = 0; i < copy1.length; i++) {
            cmp = Integer.compare(copy1[i], copy2[i]);
            if (cmp != 0) {
                return cmp;
            }
        }
        return 0;
    }
}

Answer 2

Lo que parece querer es un conjunto de enteros, y si el orden relativo es importante para usted, puede usar algo como esto:

import java.util.Set;
import java.util.LinkedHashSet;
import java.util.Arrays;
import java.util.stream.Collectors;

public class HelloWorld
{
  public static void main(String[] args)
  {
        Set<Set<Integer>> result = new LinkedHashSet<>();
        int[] x = {1, 2, 3};
        int[] z = {2, 1, 3};
        int[] m = {2, 1, 3};

        result.add(Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(z).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(m).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));

        System.out.println(result);
  }
}

También puede extraer Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)) en una función separada.

Answer 3

Puede crear un método para agregar, si no es igual, así:

public static Set<int[]> addIfNotExist(Set<int[]> result, int[] array) {
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                Arrays.sort(array);
                return Arrays.equals(a, array);
            });
    if (check) {
        return result;
    } else {
        result.add(array);
        return result;
    }
}

Entonces puedes llamar a tu método así:

result = addIfNotExist(result, x);
result = addIfNotExist(result, z);
result = addIfNotExist(result, m);

Salida

[1, 2, 3]

O si usa un Set estático, puede usar:

static Set<int[]> result = new LinkedHashSet<>();

public static void main(String[] args) {

    int[] x = {1, 2, 3};
    int[] z = {2, 1, 3};
    int[] m = {2, 1, 3};

    addIfNotExist(result, x);
    addIfNotExist(result, z);
    addIfNotExist(result, m);

    for (int[] arr : result) {
        System.out.println(Arrays.toString(arr));
    }
}

public static void addIfNotExist(Set<int[]> result, int[] array) {
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                Arrays.sort(array);
                return Arrays.equals(a, array);
            });
    if (!check) {
        result.add(array);
    }
}

Answer 4

Puede crear una clase contenedora que contendrá una variable de instancia inmutable de matriz de enteros y anulará el código hash:

public class ArrayWrapper {
   private final int[] a;

@Override
public int hashCode(){
 //your implementation 
}
@Override
 public boolean equals(){
  // your implementation 
 }
}

Y luego puedes usar:

Set<ArrayWrapper> set = new HashSet<>();

Answer 5

Ya ha habido algunas respuestas, pero algunas de ellas hacen ciertas suposiciones que no pueden derivarse de la pregunta, otras sugieren ciertos cambios que pueden considerarse como soluciones alternativas, y otras tienen ciertos inconvenientes que no deben ignorarse.

Abordar algunos de ellos aquí:

• Cambiar los elementos a un Set<Integer> supone que cada elemento solo puede aparecer una vez . Además, si el código existente ya crea las matrices int[] , y el código descendente necesita las matrices int[] , entonces usar la estructura de datos resultante sería torpe:

  int array[] = somewhere.getArray();
  Set<Integer> set = convert(array); // Convert array to set
  data.add(set);
  ...
  set = data.iterator().next();
  array = convert(set);              // Convert set to array
  somewhere.setArray(array);

  Dependiendo del tamaño de las matrices, esto puede tener un impacto en el rendimiento y generar un exceso de memoria.

• Usar un TreeSet<int[]> parece una solución simple y razonable. Lo mejor es que puede almacenar directamente las matrices int[] . Pero tiene algunos inconvenientes:

  1. Implica un pedido. Ya no es posible usar otra implementación de Set (como LinkedHashSet ) que retiene el orden de inserción
  2. Puede ser un poco complicado implementar la comparación de una manera que sea consistente con equals , y si no lo hace, el conjunto ya no obedecerá el contrato general de la interfaz Set
  3. Una implementación simple pero correcta de la comparación probablemente implicará ordenar los arreglos. Esto significa que las matrices podrían tener que modificarse mediante su inserción en el conjunto, lo que ciertamente no es aceptable, o uno tendría que crear copias defensivas de las matrices. Aquí, uno debe tener en cuenta que la copia y la clasificación deberán realizarse cada vez que se agregue una nueva matriz, y deberán realizarse varias veces mientras se baja el árbol. Aunque el número de comparaciones solo será O (log (n)) para un conjunto con n elementos, la ordenación tomará O (m log (m)) cada vez para conjuntos de longitud m , que pueden ser prohibitivamente costosos.
• Se pueden aplicar argumentos similares para los enfoques que verifican si ya existe una matriz "equivalente" antes de insertar una nueva. Además, estos enfoques no se basan en una estructura de datos, sino que deben ser parte del código que utiliza la estructura de datos.

Por estas razones, optaría por un enfoque que es básicamente el mismo que Mykhailo Moskura mencionó en su respuesta : se basa en una clase que simplemente envuelve las matrices int[] e implementa equals y hashCode consecuencia.

(Tenga en cuenta que también podría permitir que esta clase implemente Comparable , agregando cierta flexibilidad sobre si se puede poner en un TreeSet , si conoce las posibles dificultades y desventajas mencionadas anteriormente ...)

En el siguiente ejemplo, esta clase se llama UnorderedIntArray . Conceptualmente , sería preferible tener un Set<int[]> , y la solución a continuación debe usar un Set<UnorderedIntArray> . Pero dado que esta clase solo envuelve una matriz existente, el rendimiento y la sobrecarga de memoria son prácticamente cero y, por lo tanto, todavía lo considero ventajoso en comparación con la conversión entre int[] y algún otro tipo de datos. También tenga en cuenta que el método de equals en el siguiente ejemplo no es muy eficiente, pero es una forma simple de garantizar que se cumplan los contratos de equals .

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class UniqueArraysTest {

    public static void main(String[] args) {
        Set<UnorderedIntArray> result = new LinkedHashSet<>();
        int[] x = { 1, 2, 3 };
        int[] y = { 2, 1, 3 };
        int[] z = { 2, 1, 3 };

        int[] u = { 1, 1, 1, 2, 3 };
        int[] v = { 1, 1, 1, 2, 3 };
        int[] w = { 1, 1, 1, 1, 3 };

        result.add(new UnorderedIntArray(x));
        result.add(new UnorderedIntArray(y));
        result.add(new UnorderedIntArray(z));
        result.add(new UnorderedIntArray(u));
        result.add(new UnorderedIntArray(v));
        result.add(new UnorderedIntArray(w));

        for (UnorderedIntArray a : result) {
            int[] array = a.getArray();
            System.out.println(Arrays.toString(array));
        }

    }

    static class UnorderedIntArray {
        private final int array[];

        UnorderedIntArray(int array[]) {
            this.array = array;
        }

        int[] getArray() {
            return array;
        }

        @Override
        public int hashCode() {
            return IntStream.of(array).sum();
        }

        @Override
        public boolean equals(Object object) {
            if (object == this) {
                return true;
            }
            if (object == null) {
                return false;
            }
            if (!(object instanceof UnorderedIntArray)) {
                return false;
            }
            UnorderedIntArray that = (UnorderedIntArray)object;
            if (this.array.length != that.array.length) {
                return false;
            }
            // This is very simple, but not very efficient. More efficient
            // solutions could be implemented, but they are not trivial...
            Map<Integer, Long> thisFrequencies = computeFrequencies(this.array);
            Map<Integer, Long> thatFrequencies = computeFrequencies(that.array);
            return thisFrequencies.equals(thatFrequencies);
        }

        private Map<Integer, Long> computeFrequencies(int array[]) {
            return Arrays.stream(array).boxed().collect(
                Collectors.groupingBy(Function.identity(), Collectors.counting()));
        }

        @Override
        public String toString() {
            return Arrays.toString(array);
        }

    }
}

Para la entrada de

int[] x = { 1, 2, 3 };
int[] y = { 2, 1, 3 };
int[] z = { 2, 1, 3 };
int[] u = { 1, 1, 1, 2, 3 };
int[] v = { 1, 1, 1, 2, 3 };
int[] w = { 1, 1, 1, 1, 3 };

la salida es la esperada

[1, 2, 3]
[1, 1, 1, 2, 3]
[1, 1, 1, 1, 3]

Answer 6

Si suponemos que sus matrices no pueden contener varias veces el mismo número entero (como [1, 1, 2] ), entonces su definición de unicidad (que tiene los mismos elementos independientemente del orden) para su matriz es la de un Conjunto, por lo que podría usar un conjunto de conjunto.

public static void main(String[] args){
    Set<Set<Integer>> result = new HashSet<>();
    int [] x = {1,2,3};
    int [] z = {2,1,3};
    int [] m = {2,1,3};

    result.add(arrayToSet(x));
    result.add(arrayToSet(z));
    result.add(arrayToSet(m));

    System.out.println(result);

}

private static Set<Integer> arrayToSet(int [] arr){
    return Arrays.stream(arr).boxed().collect(Collectors.toSet());
}

Si desea mantener sus matrices, ¿cuál debe mantenerse cuando dos matrices tienen los mismos elementos? Si es el primero que se ha agregado, puede usar un Map<Set<Integer>, int[]> y luego los valores de su mapa contienen las matrices.

Si necesita considerar que puede contener varias veces el mismo número entero , entonces esos son Multisets . Puede implementar un Multiset mediante un Map<Integer, Integer> que cuenta la cantidad de tiempo que cada elemento está presente. Entonces puede usar la misma implementación pero con un Set<Map<Integer, Integer>> lugar de un Set<Integer> :

public static void main(String[] args){
    Set<Map<Integer,Long>> result = new HashSet<>();
    int [] x = {1,2,3};
    int [] z = {1,2,2,3};
    int [] m = {1,2,3,2};

    result.add(arrayToMultiSet(x));
    result.add(arrayToMultiSet(z));
    result.add(arrayToMultiSet(m));

    System.out.println(result);

}

private static Map<Integer,Long> arrayToMultiSet(int [] arr){
    return Arrays.stream(arr).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}

Nota: Usé Map<Integer,Long> porque Collectors.counting() devuelve un recopilador de Long .

Answer 7

@Test
    public void testArraysSet() {
        Set<int[]> myArrays = new TreeSet<>((arr1, arr2) -> {
            Arrays.sort(arr1);
            Arrays.sort(arr2);
            return Arrays.equals(arr1, arr2) ? 0 : 1;
        });

        int [] a = {1,2,3};
        int [] b = {2,1,3};
        int [] c = {2,1,3};

        myArrays.add(a);
        myArrays.add(b);
        myArrays.add(c);

        assertEquals(1, myArrays.size());
    }

Esto debería hacer, la clasificación podría ralentizar un poco las cosas. Es posible que desee ver una comparación de matriz más rápida.