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

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 enteros deberían ser 1, 2, 4, 5, 8, 10, 16, 20, 25, …

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

La idea básica es que 1 es un miembro del conjunto, y para cada miembro del conjunto n 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.

Busque “Número Hamming” o “número regular” o vaya a A003592 para obtener más información.

—– AÑADIDO MÁS TARDE —–

Decidí dedicar unos minutos en mi hora del almuerzo a escribir un progtwig para implementar el algoritmo descrito anteriormente, utilizando el lenguaje de progtwigción Scheme. En primer lugar, aquí hay una implementación de la biblioteca de colas de prioridad usando el algoritmo de montón de emparejamiento:

(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 elementos para enviar desde el 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 ((nn) (p 0) (pq (pq-insert < 1 pq-empty)) (xs (list))) (cond ((zero? n) (reverse xs)) ((= (pq-first pq) p) (loop np (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 Scheme, loop es una función definida localmente que se llama recursivamente, y cond es el jefe de una cadena if-else; 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) termina 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 rest 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 va a generar, 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 hijos del número actual e inserta el encabezado actual de la cola de prioridad en la salida de acumulación.

Como no es trivial actualizar la cola de prioridad para agregar los nuevos secundarios del número actual, esa 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))))) 

La función realiza un bucle sobre los elementos del conjunto ps , 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 de 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.

Aquí hay 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 progtwig en http://ideone.com/sA1nn .

Eliminar un número y reinsertar todos sus múltiplos (por los números primos en el conjunto) en una cola de prioridad es incorrecto (en el sentido de la pregunta), es decir, produce la secuencia correcta pero de manera ineficiente .

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 e insert usualmente no son ambas O (1) , ciertamente no en ninguna implementación de PriorityQueue basada en la lista o en el árbol).

El algoritmo O (n) eficiente mantiene los punteros en la secuencia misma mientras se produce, para encontrar y agregar 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, avanza su puntero, mientras que al mismo tiempo calcula su siguiente valor múltiple. Esto implementa de manera muy efectiva una PriorityQueue pero con distinciones cruciales: es antes del 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 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, basada en el conjunto de 3 primos, como n 2 / 3 , para n números de la secuencia).


La secuencia clásica de Hamming en 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 xy of LT -> x : union xs b EQ -> x : union xs ys GT -> y : union a ys 

Podemos generar los números uniformes para primos de base arbitrarios usando la función foldi (ver Wikipedia ) para doblar las listas en forma de árbol para la eficiencia, creando un árbol de comparaciones de tamaño fijo:

 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 fz [] = z foldi fz (x:xs) = fx (foldi fz (pairs f xs)) pairs f (x:y:t) = fxy : pairs ft pairs ft = t 

También es posible calcular directamente una porción de la secuencia de Hamming alrededor de su n. ° miembro en el tiempo O (n 2/3 ) , mediante la enumeración directa de las tripletas y evaluar sus valores a través de logaritmos, logval(i,j,k) = i*log 2+j*log 3+k*log 5 . Esta entrada de prueba de Ideone.com calcula el número de mil millones de Hamming en 1.12 0.05 segundos (2016-08-18: aceleración principal debido al uso de Int lugar del Integer predeterminado donde sea posible, incluso en 32 bits, 20% adicional gracias al ajuste sugerido por @GordonBGood, bajando la complejidad del tamaño de la banda a O (n 1/3 )).

Esto se discute más en esta respuesta donde también encontramos su atribución completa:

 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 también se puede generalizar para k primos base, probablemente corriendo en O (n (k-1) / k ) tiempo.


ver esta entrada SO para un importante desarrollo posterior. también, esta respuesta es interesante. y otra respuesta relacionada .

Este algoritmo de exploración bidimensional no es exacto, pero funciona para los primeros 25 enteros, luego mezcla 625 y 512.

Poderes de 2 y 5

 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 

En función de la respuesta del usuario448810, esta es una solución que usa montones y vectores del STL.
Ahora, los montones normalmente generan el valor más grande, por lo que almacenamos el valor negativo de los números como una solución alternativa (ya que a>b < ==> -a< -b ).

 #include  #include  #include  int main() { std::vector primes; primes.push_back(2); primes.push_back(5);//Our prime numbers that we get to use std::vector heap;//the heap that is going to store our possible values heap.push_back(-1); std::vector 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