Generar combinaciones ordenadas por un atributo

Question

Estoy buscando una manera de generar combinaciones de objetos ordenados por un solo atributo. No creo orden lexicográfico es lo que estoy buscando ... Voy a tratar de dar un ejemplo. Digamos que tengo una lista de objetos A, B, C, D con los valores de los atributos que desea ordenar por ser 3,3,2,1. Esto da objetos A3, B3, C2, D1. Ahora quiero para generar combinaciones de 2 objetos, pero necesitan ser ordenados de manera descendente:

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

Generación de todas las combinaciones y clasificación de ellos no es aceptable debido a que el escenario del mundo real implica conjuntos grandes y millones de combinaciones. (Conjunto de 40, el orden de 8), y necesito sólo combinaciones anteriores el umbral determinado.

En realidad necesito recuento de combinaciones por encima de un umbral agrupados por una suma de un atributo dado, pero creo que es mucho más difícil de hacer - lo que me conformaría con el desarrollo de todas las combinaciones por encima de un umbral y contarlos. Si eso es posible en absoluto.

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

que estaba buscando en un problema de suma subconjunto, pero si he entendido correctamente dado solución dinámica que sólo le dará información está ahí una suma determinada o no, no es la cuenta de las sumas.

Gracias

Answer 1

En realidad, creo que no quiero orden lexicográfico, pero descendiendo en lugar de ascender. Además:

• No está claro a mí de su descripción que A, B, D ... juega ningún 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 la posible máximo total de dos valores, el número de distintos pares del conjunto {3, 3, 2, 1} tienen sumas de ese entero? "
• La parte interesante es el rescate temprano, una vez que no hay solución posible puede ser alcanzado (restantes sumas alcanzables son demasiado pequeños).

Voy a publicar código de ejemplo más adelante.

Aquí está el código de ejemplo 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;
    }

}

Prefacio observaciones:

Esto utiliza un poco de clase auxiliar llamada Tally, que acaba aísla la tabulación (incluyendo la inicialización de las llaves nunca antes visto). Voy a poner al final.

Para mantener esta concisa, he tomado algunos accesos directos que no son buenas prácticas para el "verdadero" código:

• Esto no comprueba para una matriz de valor nulo, etc.
• Asumo que la matriz de valores ya está ordenada en orden descendente, requerido para la técnica de principios del rescate. (Buena código de producción incluiría la clasificación.)
• pongo datos transitorios en las variables de instancia en lugar de pasarlos como argumentos entre los métodos privados que apoyan count. Eso hace que esta clase no seguro para subprocesos.

Explicación:

Una instancia de Combos se crea con la matriz (descendente ordenado) de números enteros para combinar. La matriz value está configurado una vez por ejemplo, pero varias llamadas a count se puede hacer con diferentes tamaños de población y límites.

El método count desencadena un recorrido recursivo (en su mayoría) el nivel de combinaciones únicas de números enteros n de values. El argumento limit da el límite inferior en sumas de interés.

El método countAt examina combinaciones de números enteros de values. El argumento es left cuántos números enteros permanecen para compensar enteros n en una suma, start es la posición en values la que desea buscar, y sum es la suma parcial.

El mecanismo de rescate temprano se basa en el cálculo de best, una matriz bidimensional que especifica el "mejor" suma accesible desde un estado dado. El valor en best[n][p] es la mayor suma de valores n empezando en la posición p del values originales.

La recursión de fondos countAt fuera cuando la población correcta se ha acumulado; esto se suma la sum actual (de los valores n) a la tally. Si countAt no ha tocado fondo, que se extiende por el values desde la posición start-ción para aumentar la sum parcial actual, siempre y cuando:

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

Un análisis de la muestra con los datos de la 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 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 2

He escrito una clase para manejar las funciones comunes para trabajar con el coeficiente binomial, que es el tipo de problema que su problema cae bajo. Se lleva a cabo las siguientes tareas:

1. Salidas todos los K-índices en un formato agradable para cualquier N elegir K en un archivo. Los K-índices pueden estar sustituidos con cadenas más descriptivos o letras. Este método hace que la solución de este tipo de problema bastante trivial.

2. Convierte el K-índices para el índice adecuado de una entrada en la tabla de coeficientes del binomio ordenada. Esta técnica es mucho más rápido que las técnicas publicadas de más edad que dependen de la iteración. Esto se logra mediante el uso de una propiedad matemática inherente triángulo de Pascal. Mi papel 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 binomial ordenan en las correspondientes K-índices.

4. método Marcos Dominus para calcular el coeficiente binomial, que es mucho menos propensos a desbordarse y trabaja con números más grandes.

5. La clase está escrito en C # .NET y proporciona una manera de manejar los objetos relacionados con el problema (si lo hay) mediante el uso de una lista genérica. El constructor de esta clase tiene un valor bool llamada InitTable cierto que cuando va a crear una lista genérica que tiene los objetos que deben gestionarse. Si este valor es falso, entonces no va a crear la tabla. La tabla no necesita ser creada con el fin de realizar los 4 métodos anteriores. Se proporcionan métodos de acceso para acceder a la tabla.

6. Hay una clase de prueba asociado que muestra cómo utilizar la clase y sus métodos. Se ha probado extensamente con 2 casos y no hay errores conocidos.

Para leer acerca de esta clase y descargar el código, consulte Tablizing el binomio Coeffieicent .

Answer 3

Salida esta pregunta en StackOverflow: Algoritmo para devolver toda combinación s

También acabo de utilizar un código java a continuación para generar todas las permutaciones, pero podría ser fácilmente utilizada para generar la combinación de único 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;
}

Answer 4

Estoy muy lo siento (después de todas esas aclaraciones en los comentarios) a decir que no he podido encontrar una solución eficaz a este problema. He intentado durante la última hora sin resultados.

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

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

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

Trate de clasificación de los datos de acuerdo con los atributos. Usted puede ser capaz de evitar el procesamiento de algunos valores de la lista cuando se encuentra que un valor más alto no puede satisfacer el umbral (por lo que todos los valores más bajos se pueden eliminar).

Answer 5

Si estás usando C # hay una bastante buena biblioteca genéricos aquí . Tenga en cuenta sin embargo que la generación de algunas permutaciones no está en orden lexicográfico

Answer 6

Aquí hay un enfoque recursivo a recuento el número de estos subconjuntos: Definimos una count(minIndex,numElements,minSum) función que devuelve el número de subconjuntos de tamaño numElements cuya suma es de al menos minSum, que contiene los elementos con índices minIndex o mayor .

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

Código de ejemplo (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, me he encontrado lo anterior con una serie de 40 elementos, y tamaño-8 subconjuntos y consistentemente regresar resultados en menos de un segundo.