Generar enteros en orden ascendente usando un conjunto de números primos

Question

Tengo un conjunto de números primos y tengo que generar enteros usando solo esos factores primos en orden creciente.

Por ejemplo, si el conjunto es p = {2, 5} entonces mis números enteros deben ser 1, 2, 4, 5, 8, 10, 16, 20, 25, ...

¿Hay Algún algoritmo eficiente para resolver este problema?

Answer 1

La idea básica es que 1 es un miembro del conjunto, y para cada miembro del conjunto n así también 2 n y 5 n son miembros del conjunto. Por lo tanto, comienza con la salida 1, y presione 2 y 5 en una cola de prioridad. Luego, aparece repetidamente el elemento frontal de la cola de prioridad, lo muestra si es diferente del resultado anterior y empuja 2 veces y 5 veces el número en la cola de prioridad.

Google para "Hamming number" o "número normal" o vaya a A003592 para obtener más información.

----- ----- añadió más tarde

yo decidimos pasar unos minutos en mi hora de almuerzo para escribir un programa para implementar el algoritmo descrito anteriormente, utilizando el lenguaje de programación Scheme. En primer lugar, here es una implementación de la biblioteca de colas de prioridad utilizando el algoritmo de emparejamiento montón:

(define pq-empty '()) 
(define pq-empty? null?) 

(define (pq-first pq) 
    (if (null? pq) 
     (error 'pq-first "can't extract minimum from null queue") 
     (car pq))) 

(define (pq-merge lt? p1 p2) 
    (cond ((null? p1) p2) 
     ((null? p2) p1) 
     ((lt? (car p2) (car p1)) 
      (cons (car p2) (cons p1 (cdr p2)))) 
     (else (cons (car p1) (cons p2 (cdr p1)))))) 

(define (pq-insert lt? x pq) 
    (pq-merge lt? (list x) pq)) 

(define (pq-merge-pairs lt? ps) 
    (cond ((null? ps) '()) 
     ((null? (cdr ps)) (car ps)) 
     (else (pq-merge lt? (pq-merge lt? (car ps) (cadr ps)) 
          (pq-merge-pairs lt? (cddr ps)))))) 

(define (pq-rest lt? pq) 
    (if (null? pq) 
     (error 'pq-rest "can't delete minimum from null queue") 
     (pq-merge-pairs lt? (cdr pq)))) 

Ahora para el algoritmo. La función f toma dos parámetros, una lista de los números en el conjunto ps y el número n de los elementos a la salida del encabezado de la salida. El algoritmo está ligeramente cambiado; la cola de prioridad se inicializa presionando 1, luego comienzan los pasos de extracción. La variable p es el valor de salida anterior (inicialmente 0), pq es la cola de prioridad, y xs es la lista de salida, que se acumula en orden inverso. Aquí está el código:

(define (f ps n) 
    (let loop ((n n) (p 0) (pq (pq-insert < 1 pq-empty)) (xs (list))) 
    (cond ((zero? n) (reverse xs)) 
      ((= (pq-first pq) p) (loop n p (pq-rest < pq) xs)) 
      (else (loop (- n 1) (pq-first pq) (update < pq ps) 
         (cons (pq-first pq) xs)))))) 

Para aquellos que no están familiarizados con el esquema, loop es una función definida a nivel local que se llama de forma recursiva, y cond es la cabeza de una cadena else if-; en este caso, hay tres cláusulas cond, cada cláusula con un predicado y consecuente, con el consecuente evaluado para la primera cláusula para la cual el predicado es verdadero. El predicado (zero? n) finaliza la recursión y devuelve la lista de salida en el orden correcto. El predicado (= (pq-first pq) p) indica que el encabezado actual de la cola de prioridad se ha emitido previamente, por lo que se omite recurriendo con el resto de la cola de prioridad después del primer elemento. Finalmente, el predicado else, que siempre es verdadero, identifica un nuevo número que se saldrá, por lo que disminuye el contador, guarda el encabezado actual de la cola de prioridad como el nuevo valor anterior, actualiza la cola de prioridad para agregar los nuevos secundarios del número actual e inserta el encabezado actual de la cola de prioridad en la salida de acumulación.

Ya que no es trivial para actualizar la cola de prioridad para añadir los nuevos niños del número actual, que la operación se extrae a una función separada:

(define (update lt? pq ps) 
    (let loop ((ps ps) (pq pq)) 
    (if (null? ps) (pq-rest lt? pq) 
     (loop (cdr ps) (pq-insert lt? (* (pq-first pq) (car ps)) pq))))) 

Los bucles de función sobre los elementos de la ps establecer, insertando cada uno en la cola de prioridad a su vez; el if devuelve la cola de prioridad actualizada, menos su cabeza anterior, cuando se agota la lista ps. El paso recursivo quita el encabezado de la lista ps con cdr e inserta el producto del encabezado de la cola de prioridad y el encabezado de la lista ps en la cola de prioridad.

Éstos son dos ejemplos del algoritmo:

> (f '(2 5) 20) 
(1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250) 
> (f '(2 3 5) 20) 
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36) 

puede ejecutar el programa en http://ideone.com/sA1nn.

Answer 2

Este algoritmo de exploración de 2 dimensiones no es exacta, pero funciona para los primeros 25 números enteros, a continuación, se mezcla hasta 625 y 512.

n = 0 
exp_before_5 = 2 
while true 
    i = 0 
    do 
    output 2^(n-exp_before_5*i) * 5^Max(0, n-exp_before_5*(i+1)) 
    i <- i + 1 
    loop while n-exp_before_5*(i+1) >= 0 
    n <- n + 1 
end while 

Answer 3

Sobre la base de la respuesta de user448810, he aquí una solución que usa montones y vectores del STL.
Ahora, los montones normalmente producen el valor más grande, por lo que almacenamos el negativo de los números como una solución (desde a>b <==> -a<-b).

#include <vector> 
#include <iostream> 
#include <algorithm> 

int main() 
{ 
    std::vector<int> primes; 
    primes.push_back(2); 
    primes.push_back(5);//Our prime numbers that we get to use 

    std::vector<int> heap;//the heap that is going to store our possible values 
    heap.push_back(-1); 
    std::vector<int> outputs; 
    outputs.push_back(1); 
    while(outputs.size() < 10) 
    { 
     std::pop_heap(heap.begin(), heap.end()); 
     int nValue = -*heap.rbegin();//Get current smallest number 
     heap.pop_back(); 
     if(nValue != *outputs.rbegin())//Is it a repeat? 
     { 
      outputs.push_back(nValue); 
     } 
     for(unsigned int i = 0; i < primes.size(); i++) 
     { 
      heap.push_back(-nValue * primes[i]);//add new values 
      std::push_heap(heap.begin(), heap.end()); 
     } 
    } 
    //output our answer 
    for(unsigned int i = 0; i < outputs.size(); i++) 
    { 
     std::cout << outputs[i] << " "; 
    } 
    std::cout << std::endl; 
} 

Salida:

1 2 4 5 8 10 16 20 25 32 

Answer 4

Extracción de un número y volver a insertar todos sus múltiplos (por los números primos en el conjunto) en una cola de prioridad se mal (en el sentido de la pregunta) - es decir, produce la secuencia correcta pero ineficientemente así.

Es ineficiente de dos maneras: primero, produce en exceso la secuencia; segundo, cada operación PriorityQueue incurre en un costo adicional (las operaciones remove_top y insert generalmente no son ambas O (1), ciertamente no en ninguna implementación de PriorityQueue basada en la lista o en el árbol).

La eficiente algoritmo O (n) mantiene punteros de nuevo en la propia secuencia, ya que se está produciendo, para encontrar y añadir el siguiente número en O (1). En pseudocódigo:

return array h where 
    h[0]=1; n=0; ps=[2,3,5, ... ]; // base primes 
    is=[0 for each p in ps];  // indices back into h 
    xs=[p for each p in ps]  // next multiples: xs[k]==ps[k]*h[is[k]] 
    repeat: 
     h[++n] := minimum xs 
     for each (i,x,p) in (is,xs,ps): 
     if(x==h[n]) 
      { x := p*h[++i]; }  // advance the minimal multiple/pointer 

para cada múltiplo mínimo que avanza su puntero, mientras que al mismo tiempo calculando su próximo valor múltiple.Esto implementa de manera muy efectiva una PriorityQueue pero con distinciones cruciales: es antes de el punto final, no después; no crea ningún almacenamiento adicional a excepción de la secuencia misma; y su tamaño es constante (solo k números, para k primos de base) mientras que el tamaño de PriorityQueue pasa a medida que progresamos a lo largo de la secuencia (en el caso de la secuencia de Hamming, basado en el conjunto de primos, como n ^2/3, para n números de la secuencia).

---

El clásico Hamming sequence in Haskell es esencialmente el mismo algoritmo:

h = 1 : map (2*) h `union` map (3*) h `union` map (5*) h 

union a@(x:xs) b@(y:ys) = case compare x y of LT -> x : union xs b 
               EQ -> x : union xs ys 
               GT -> y : union a ys 

Podemos generar los smooth numbers para primos de base arbitrarias usando la función foldi (ver Wikipedia) para plegar las listas en un árbol-como moda para la eficiencia, la creación de un árbol de tamaño fijo de las comparaciones:

smooth base_primes = h where  -- strictly increasing base_primes NB! 
    h = 1 : foldi g [] [map (p*) h | p <- base_primes] 
    g (x:xs) ys = x : union xs ys 

foldi f z []  = z 
foldi f z (x:xs) = f x (foldi f z (pairs f xs)) 

pairs f (x:y:t) = f x y : pairs f t 
pairs f t  = t 

---

También es posible calcular directamente un rebanada de secuencia de Hamming alrededor de su ésimo miembro n en O (n ^2/3) tiempo, por enumeración directa de los triples y la evaluación de sus valores a través de logaritmos, logval(i,j,k) = i*log 2+j*log 3+k*log 5. Este Ideone.com test entry calcula 1 billionth Hamming number en 1,12 0,05 segundo _{(08/18/2016: aceleración principal debido al uso de Int en lugar del predeterminado Integer cuando sea posible, incluso en 32 bits; adicionales 20% gracias a la Tweak sugeridas por @GordonBGood, bajando la complejidad del tamaño de banda a O (n ^1/3)).}

Esto se discute un poco más en this answer, donde también se encuentra su plena atribución:

slice hi w = (c, sortBy (compare `on` fst) b) where -- hi is a top log2 value 
    lb5=logBase 2 5 ; lb3=logBase 2 3     -- w<1 (NB!) is (log2 width) 
    (Sum c, b) = fold         -- total count, the band 
     [ (Sum (i+1),         -- total triples w/this j,k 
      [ (r,(i,j,k)) | frac < w ])    -- store it, if inside the band 
     | k <- [ 0 .. floor (hi /lb5) ], let p = fromIntegral k*lb5, 
      j <- [ 0 .. floor ((hi-p)/lb3) ], let q = fromIntegral j*lb3 + p, 
      let (i,frac) = pr (hi-q)  ;  r = hi - frac -- r = i + q 
     ] -- (sum . map fst &&& concat . map snd) 
    pr = properFraction 

Esto se puede generalizar para k base de los primos, así, probablemente se ejecuta en O (n ^{(k -1)/k}) tiempo.

---

ver this SO entry para un desarrollo posterior importante. también, this answer es interesante. y otro related answer.