resueltos - matriz java filas columnas

¿Algoritmo para obtener todas las combinaciones de tamaño n de una matriz(Java)?

Question

En este momento estoy tratando de escribir una función que tome una matriz y un entero n, y ofrezca una lista de cada combinación de tamaño n (así que una lista de matrices int). Puedo escribirlo utilizando n bucles anidados, pero esto solo funciona para un tamaño específico de subconjunto. No puedo imaginar cómo generalizarlo para que funcione con cualquier tamaño de combinación. Creo que necesito usar la recursión?

Este es el código para todas las combinaciones de 3 elementos, y necesito un algoritmo para cualquier número de elementos.

import java.util.List;
import java.util.ArrayList;

public class combinatorics{
    public static void main(String[] args) {

        List<int[]> list = new ArrayList<int[]>();
        int[] arr = {1,2,3,4,5};
        combinations3(arr,list);
        listToString(list);
    }

    static void combinations3(int[] arr, List<int[]> list){
        for(int i = 0; i<arr.length-2; i++)
            for(int j = i+1; j<arr.length-1; j++)
                for(int k = j+1; k<arr.length; k++)
                    list.add(new int[]{arr[i],arr[j],arr[k]});
    }

    private static void listToString(List<int[]> list){
        for(int i = 0; i<list.size(); i++){ //iterate through list
            for(int j : list.get(i)){ //iterate through array
                System.out.printf("%d ",j);
            }
        System.out.print("/n");
        }
    }
}

Answer 1

Definitivamente puedes hacer esto con iteración.

Aquí hay una solución que calcula la cantidad de matrices que deberíamos crear y luego las construimos usando matemáticas para calcular qué elemento de la matriz de origen debería estar en qué lugar:

public static void combinations(int n, int[] arr, List<int[]> list) {
    // Calculate the number of arrays we should create
    int numArrays = (int)Math.pow(arr.length, n);
    // Create each array
    for(int i = 0; i < numArrays; i++) {
        int[] current = new int[n];
        // Calculate the correct item for each position in the array
        for(int j = 0; j < n; j++) {
            // This is the period with which this position changes, i.e.
            // a period of 5 means the value changes every 5th array
            int period = (int) Math.pow(arr.length, n - j - 1);
            // Get the correct item and set it
            int index = i / period % arr.length;
            current[j] = arr[index];
        }
        list.add(current);
    }
}

Actualizar:

Aquí hay una versión optimizada que reduce significativamente la cantidad de llamadas a Math.pow

public static void combinations(int n, int[] arr, List<int[]> list) {
    // Calculate the number of arrays we should create
    int numArrays = (int)Math.pow(arr.length, n);
    // Create each array
    for(int i = 0; i < numArrays; i++) {
        list.add(new int[n]);
    }
    // Fill up the arrays
    for(int j = 0; j < n; j++) {
        // This is the period with which this position changes, i.e.
        // a period of 5 means the value changes every 5th array
        int period = (int) Math.pow(arr.length, n - j - 1);
        for(int i = 0; i < numArrays; i++) {
            int[] current = list.get(i);
            // Get the correct item and set it
            int index = i / period % arr.length;
            current[j] = arr[index];
        }
    }
}

Answer 2

Este es un problema bien estudiado de generar todos los k-subconjuntos, o k-combinations , que se pueden hacer fácilmente sin recursión.

La idea es tener una matriz de tamaño k mantenga la secuencia de índices de elementos de la matriz de entrada (que son números de 0 a n - 1 ) en orden creciente. (El subconjunto se puede crear tomando los ítems según estos índices de la matriz inicial). Por lo tanto, necesitamos generar todas las secuencias de índices.

La primera secuencia de índice será [0, 1, 2, ... , k - 1] , en el segundo paso cambia a [0, 1, 2,..., k] y luego a [0, 1, 2, ... k + 1] y así sucesivamente. La última secuencia posible será [n - k, n - k + 1, ..., n - 1] .

En cada paso, el algoritmo busca el elemento más cercano al elemento final que puede incrementarse, lo incrementa y rellena los elementos directamente a ese elemento.

Para ilustrar, considere n = 7 y k = 3 . La primera secuencia de índice es [0, 1, 2] , luego [0, 1, 3] y así sucesivamente ... En algún punto tenemos [0, 5, 6] :

[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements

next iteration:

[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"

Así, a [0, 5, 6] le sigue [1, 2, 3] , luego va a [1, 2, 4] etc.

Código:

int[] input = {10, 20, 30, 40, 50};    // input array
int k = 3;                             // sequence length   

List<int[]> subsets = new ArrayList<>();

int[] s = new int[k];                  // here we''ll keep indices 
                                       // pointing to elements in input array

if (k <= input.length) {
    // first index sequence: 0, 1, 2, ...
    for (int i = 0; (s[i] = i) < k - 1; i++);  
    subsets.add(getSubset(input, s));
    for(;;) {
        int i;
        // find position of item that can be incremented
        for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--); 
        if (i < 0) {
            break;
        }
        s[i]++;                    // increment this item
        for (++i; i < k; i++) {    // fill up remaining items
            s[i] = s[i - 1] + 1; 
        }
        subsets.add(getSubset(input, s));
    }
}

// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
    int[] result = new int[subset.length]; 
    for (int i = 0; i < subset.length; i++) 
        result[i] = input[subset[i]];
    return result;
}

Answer 3

Si entendí tu problema correctamente, this artículo parece indicar lo que estás tratando de hacer.

Para citar del artículo:

Método 1 (arreglar elementos y repetir)

Creamos una matriz temporal ''datos []'' que almacena todas las salidas una por una. La idea es comenzar desde el primer índice (índice = 0) en los datos [], uno por uno, corregir elementos en este índice y volver a aparecer para los índices restantes. Deje que la matriz de entrada sea {1, 2, 3, 4, 5} yr sea 3. Primero reparamos 1 en el índice 0 en los datos [], luego repetimos para los índices restantes, luego corregimos 2 en el índice 0 y recurrimos. Finalmente, arreglamos 3 y recurrimos para los índices restantes. Cuando el número de elementos en los datos [] se vuelve igual a r (tamaño de una combinación), imprimimos los datos [].

Método 2 (incluir y excluir cada elemento)

Al igual que el método anterior, creamos una matriz temporal de datos []. La idea aquí es similar a Subset Sum Problem. Nosotros, uno por uno, consideramos cada elemento de la matriz de entrada, y recurrimos para dos casos:

1. El elemento se incluye en la combinación actual (Ponemos el elemento en datos [] e incrementamos el siguiente índice disponible en datos [])
2. El elemento se excluye en la combinación actual (no colocamos el elemento y no cambiamos el índice)

Cuando el número de elementos en los datos [] se vuelve igual a r (tamaño de una combinación), lo imprimimos.