sum - estadistica - tipos de permutaciones

Generar combinaciones ordenadas por un atributo

Question

Estoy buscando una forma de generar combinaciones de objetos ordenados por un solo atributo. No creo que el orden lexicográfico sea lo que estoy buscando ... Trataré de dar un ejemplo. Digamos que tengo una lista de los objetos A, B, C, D con los valores de atributo que quiero ordenar al ser 3,3,2,1. Esto le da objetos A3, B3, C2, D1. Ahora quiero generar combinaciones de 2 objetos, pero deben ordenarse de forma descendente:

• A3 B3
• A3 C2
• B3 C2
• A3 D1
• B3 D1
• C2 D1

Generar todas las combinaciones y clasificarlas no es aceptable porque el escenario del mundo real involucra conjuntos grandes y millones de combinaciones. (conjunto de 40, orden de 8), y solo necesito combinaciones por encima del umbral determinado.

En realidad, necesito contar las combinaciones por encima de un umbral agrupado por la suma de un atributo dado, pero creo que es mucho más difícil de hacer, así que me conformaría con desarrollar todas las combinaciones por encima de un umbral y contarlas. Si eso es posible en absoluto.

EDITAR - Mi pregunta original no era muy precisa ... En realidad no necesito estas combinaciones ordenadas, solo pensé que ayudaría a aislar las combinaciones por encima de un umbral. Para ser más precisos, en el ejemplo anterior, dando un umbral de 5, estoy buscando una información que el conjunto dado produzca 1 combinación con una suma de 6 (A3 B3) y 2 con una suma de 5 (A3 C2, B3 C2). Realmente no necesito las combinaciones.

Estaba investigando un problema de suma de subconjuntos, pero si entendí correctamente la solución dinámica, solo le dará información si hay una suma determinada o no, no cuenta de las sumas.

Gracias

Answer 1

Aquí hay un enfoque recursivo para contar el número de estos subconjuntos: definimos un count(minIndex,numElements,minSum) función count(minIndex,numElements,minSum) que devuelve el número de subconjuntos de tamaño numElements cuya suma es al menos minSum , que contiene elementos con índices minIndex o superior.

Como en el enunciado del problema, ordenamos nuestros elementos en orden descendente, por ejemplo [3,3,2,1], y llamamos al primer índice cero y al número total de elementos N. Suponemos que todos los elementos son no negativos. Para encontrar los 2 subconjuntos cuya suma es al menos 5, llamamos count(0,2,5) .

Código de muestra (Java):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

Por cierto, he ejecutado lo anterior con una matriz de 40 elementos y subconjuntos de tamaño 8 y obtuve resultados consistentemente en menos de un segundo.

Answer 2

En realidad, creo que quieres un orden lexicográfico, pero descendente en lugar de ascendente. En adición:

• No me queda claro por su descripción que A, B, ... D desempeñan un papel en su respuesta (excepto posiblemente como contenedor de los valores).
• Creo que su ejemplo de pregunta es simplemente "Para cada número entero al menos 5, hasta el máximo posible total de dos valores, ¿cuántos pares distintos del conjunto {3, 3, 2, 1} tienen sumas de ese número entero?"
• La parte interesante es el rescate anticipado, una vez que no se puede llegar a una solución posible (las sumas restantes alcanzables son demasiado pequeñas).

Voy a publicar código de muestra más tarde.

Aquí está el código de muestra que prometí, con algunas observaciones siguientes:

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

Observaciones previas:

Esto usa una pequeña clase de ayuda llamada Tally, que solo aísla la tabulación (incluida la inicialización de las claves nunca antes vistas). Lo pondré al final.

Para mantener esto conciso, tomé algunos atajos que no son una buena práctica para el código "real":

• Esto no comprueba una matriz de valores nulos, etc.
• Supongo que la matriz de valores ya está ordenada en orden descendente, necesaria para la técnica de rescate anticipado. (Un buen código de producción incluiría la clasificación).
• Puse datos transitorios en variables de instancia en lugar de pasarlos como argumentos entre los métodos privados que admiten el count . Eso hace que esta clase no sea segura para subprocesos.

Explicación:

Se crea una instancia de Combos con la matriz (descendente ordenada) de enteros para combinar. El conjunto de value se configura una vez por instancia, pero se pueden realizar múltiples llamadas para count con diferentes tamaños de población y límites.

El método de count desencadena un cruce recursivo (principalmente) estándar de combinaciones únicas de n enteros de values . El argumento de limit da el límite inferior en sumas de interés.

El método countAt examina combinaciones de enteros a partir de values . El argumento de la left es cuántos enteros quedan para formar n enteros en una suma, start es la posición en los values partir de los cuales buscar, y sum es la suma parcial.

El mecanismo de rescate anticipado se basa en la best computación, una matriz bidimensional que especifica la "mejor" suma alcanzable desde un estado dado. El valor en best[n][p] es la suma más grande de n valores que comienzan en la posición p de los values originales.

La recursión de countAt fondo cuando se ha acumulado la población correcta; esto agrega la sum actual (de n valores) a la tally . Si countAt no tocó fondo, barre los values desde la posición start para aumentar la sum parcial actual, siempre que:

• suficientes posiciones permanecen en values para alcanzar la población especificada, y
• el best (más grande) subtotal restante es lo suficientemente grande como para hacer el limit .

Un ejemplo de ejecución con los datos de su pregunta:

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

produce los resultados que ha especificado:

found 2 sums of 5
found 1 sums of 6

Aquí está el código de Tally:

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

Answer 3

Lamento profundamente (después de todas las aclaraciones en los comentarios) decir que no pude encontrar una solución eficiente a este problema. Lo intenté durante la última hora sin resultados.

La razón (creo) es que este problema es muy similar a problemas como el problema del vendedor ambulante. Hasta que a menos que pruebe todas las combinaciones, no hay forma de saber qué atributos se agregarán hasta el umbral.

No parece haber ningún truco inteligente que pueda resolver esta clase de problemas.

Todavía hay muchas optimizaciones que puede hacer con el código real.

Intenta ordenar los datos según los atributos. Es posible que pueda evitar el procesamiento de algunos valores de la lista cuando descubra que un valor más alto no puede satisfacer el umbral (por lo que se pueden eliminar todos los valores más bajos).

Answer 4

Si usa C #, hay una biblioteca de genéricos bastante buena aquí . Sin embargo, tenga en cuenta que la generación de algunas permutaciones no está en orden lexicográfico

Answer 5

He escrito una clase para manejar las funciones comunes para trabajar con el coeficiente binomial, que es el tipo de problema al que se enfrenta su problema. Realiza las siguientes tareas:

1. Emite todos los índices K en un formato agradable para cualquier N elija K en un archivo. Los índices K pueden sustituirse por cadenas o letras más descriptivas. Este método hace que resolver este tipo de problema sea bastante trivial.

2. Convierte los índices K al índice apropiado de una entrada en la tabla de coeficientes binomiales ordenados. Esta técnica es mucho más rápida que las técnicas publicadas más antiguas que se basan en la iteración. Hace esto usando una propiedad matemática inherente al Triángulo de Pascal. Mi periódico habla de esto. Creo que soy el primero en descubrir y publicar esta técnica, pero podría estar equivocado.

3. Convierte el índice en una tabla de coeficientes binomiales ordenados a los índices K correspondientes.

4. Utiliza el método de Mark Dominus para calcular el coeficiente binomial, que es mucho menos probable que se desborde y funciona con números más grandes.

5. La clase está escrita en .NET C # y proporciona una forma de administrar los objetos relacionados con el problema (si corresponde) mediante el uso de una lista genérica. El constructor de esta clase toma un valor bool llamado InitTable que cuando sea verdadero creará una lista genérica para contener los objetos que se administrarán. Si este valor es falso, no creará la tabla. No es necesario crear la tabla para realizar los 4 métodos anteriores. Se proporcionan métodos de acceso para acceder a la tabla.

6. Hay una clase de prueba asociada que muestra cómo usar la clase y sus métodos. Ha sido ampliamente probado con 2 casos y no hay errores conocidos.

Para leer sobre esta clase y descargar el código, vea Tablizing The Binomial Coeffieicent .

Answer 6

Mira esta pregunta en : Algoritmo para devolver todas las combinaciones

También usé el código java a continuación para generar todas las permutaciones, pero podría usarse fácilmente para generar una combinación única dado un índice.

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}