python - todas - Generar combinaciones de enteros por suma mínima

permutacion de una lista python

Question

Mi problema radica en generar combinaciones únicas de una gran lista ordenada de números primos, elegir 5, pero necesito que se devuelvan las combinaciones de modo que las combinaciones con las sumas más pequeñas se devuelvan primero. La función python itertools.combinations() devuelve los números, aumentando el final hasta llegar al final del objeto iterable antes de aumentar el siguiente, etc. Esto no es adecuado para mi proyecto porque la suma seguirá aumentando hasta que llegue al elemento final de mi conjunto de primos, en cuyo punto la suma caerá antes de aumentar de nuevo.

Por ejemplo, si tengo un pequeño conjunto de primos {2,3,5,7,11,13,17,19,23,29} , necesitaría que las combinaciones se devuelvan en este orden:

    (2, 3, 5, 7, 11)    sum = 28
    (2, 3, 5, 7, 13)    sum = 30
    (2, 3, 5, 7, 17)    sum = 34
    (2, 3, 5, 11, 13)   sum = 34
    (2, 3, 5, 7, 19)    sum = 36
    (2, 3, 7, 11, 13)   sum = 36
    (2, 3, 5, 11, 17)   sum = 38
    (2, 5, 7, 11, 13)   sum = 38
    (3, 5, 7, 11, 13)   sum = 39
    (2, 3, 5, 7, 23)    sum = 40
    (2, 3, 5, 11, 19)   sum = 40
    (2, 3, 5, 13, 17)   sum = 40
    (2, 3, 7, 11, 17)   sum = 40
    (2, 3, 5, 13, 19)   sum = 42
    (2, 3, 7, 11, 19)   sum = 42
    (2, 3, 7, 13, 17)   sum = 42
    (2, 5, 7, 11, 17)   sum = 42
    ...

El orden de dos conjuntos con la misma suma no tiene importancia, siempre que un generador con una suma mayor no sea devuelto por un generador antes de un conjunto con una suma menor. El conjunto de números primos con los que estoy trabajando contiene aproximadamente 100,000 elementos, lo que significa que simplemente generar todas las combinaciones y ordenarlas es increíblemente inviable, ya que requeriría espacio para 83,325,000,291,662,500,020,000 tuplas de 5 enteros cada una. Además, cada elemento en la tupla de combinaciones devuelta debe ser único; no puede haber enteros repetidos. ¿Algunas ideas?

Answer 1

En lugar de generar combinaciones y sumarlas, pruébelas al revés: dada una secuencia de sumas, genere combinaciones para cada suma:

# some primes for tesing
primes = [2]
x = 3
while x < 100000:
    if all(x % p for p in primes):
        primes.append(x)
    x += 2

# main code

def find(tsum, tlen):

    def _find(tsum, tlen, path, idx):
        if tlen <= 0:
            if tsum == 0:
                yield path
            return
        while True:
            p = primes[idx]
            if p > tsum:
                return
            for f in _find(tsum - p, tlen - 1, path + [p], idx + 1):
                yield f
            idx += 1

    return _find(tsum, tlen, [], 0)

for s in range(1001, 1002): # just for testing, should be range(28, max possible sum)
    for comb in find(s, 5):
        print s, comb

Esto está lejos de ser ideal en términos de rendimiento, pero aún bastante rápido en mi máquina.

Answer 2

No estoy seguro de cuánto espacio necesitaría, así que mejor intente primero con un conjunto de primos más pequeño.

• Tenga una matriz / una lista de los números primos, ordenados en orden ascendente.

• Mantenga una cola de prioridad de quíntuplos de índice, con la suma de los primos correspondientes como la clave / peso / prioridad / cita de whada, inicialmente llena con el quíntuplo (0,1,2,3,4) de peso 2+3+5+7+11 = 28 .

• Mientras la cola no está vacía,

  1. obtener el quíntuplo con la suma más pequeña de la cola, decir (a, b, c, d, e, f) (eliminarlo, por supuesto).

  2. inserte los sucesores directos de la cola, los sucesores son los de

     • (a+1,b,c,d,e)
     • (a,b+1,c,d,e)
     • (a,b,c+1,d,e)
     • (a,b,c,d+1,e)
     • (a,b,c,d,e+1)

     que son estrictamente ascendentes y tienen el último componente más pequeño que la longitud de la lista principal

  3. ceda el quintuplo obtenido anteriormente

Answer 3

SI puede ayudarte , aquí hay un programa en C que casi genera combinaciones de enteros por una suma mínima. Los enteros se deben dar en orden ascendente. Este programa se hereda del otro programa en esta publicación :

#include <stdio.h>
#include <stdlib.h>
int v[100], stack[100];
int sp,i,j,k,n,g,s;
int main()
{
    printf("Dimension of V:");
    scanf( "%d",&n);
    //Input numbers
    for (i=0 ; i<n ; i++) {
        printf("V[%d]=",i);
        scanf( "%d",&g);
        v[i]=g;
    }
    printf("subset number:");
    scanf( "%d",&k);
    printf("running.../n");
    j=0;
    s=0;
    sp=-1;
    while(1) {
        // stack ones until 
        while(sp<n-1 && j<k && n-sp>k-j)  {
            j=j+1;
            sp=sp+1;
            stack[sp]=1;
            s=s+v[sp];
            if(j==k) {
                for (i=0 ; i<=sp ; i++) if (stack[i]==1) printf("%2d ",v[i]);
                printf("sum=%d/n",s);
            }
        }
        // unstack all the zeros until top of stack is equal one
        while (stack[sp]==0 && sp>=0) sp=sp-1;
        // if Bottom of stack is reached then stop
        if (sp<0) break;
        // set top of stack from one to zero
        stack[sp]=0;
        s=s-v[sp];
        j=j-1;
    }
    return 0;
}