Generare numeri interi in ordine crescente usando un numero di numeri primi

Question

Ho un set di numeri primi e devo generare numeri interi usando solo quei fattori primi in ordine crescente.

Per esempio, se il set è p = {2, 5} poi i miei interi dovrebbero essere 1, 2, 4, 5, 8, 10, 16, 20, 25, ...

C'è qualsiasi algoritmo efficiente per risolvere questo problema?

Answer 1

L'idea di base è che 1 è un membro del set, e per ogni membro del set n così anche 2 n e 5 n fanno parte del set. Quindi, inizi a emettere 1 e premi 2 e 5 su una coda di priorità. Quindi, si apre ripetutamente l'elemento anteriore della coda di priorità, lo si emette se è diverso dall'uscita precedente e si preme 2 volte e 5 volte il numero sulla coda di priorità.

Google per "numero di Hamming" o "numero normale" o andare a A003592 per saperne di più.

----- ----- aggiunto in seguito

ho deciso di trascorrere qualche minuto sulla mia ora di pranzo di scrivere un programma per implementare l'algoritmo descritto sopra, usando il linguaggio di programmazione Scheme. In primo luogo, here è un'implementazione libreria di code di priorità che utilizzano l'algoritmo heap abbinamento:

(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)))) 

Ora per l'algoritmo. La funzione f accetta due parametri, un elenco dei numeri nel set ps e il numero n di elementi da emettere dalla testina dell'output. L'algoritmo è leggermente cambiato; la coda di priorità viene inizializzata premendo 1, quindi vengono avviati i passaggi di estrazione. Variabile p è il valore di uscita precedente (inizialmente 0), pq è la coda di priorità e xs è l'elenco di output, che viene accumulato in ordine inverso. Ecco il codice:

(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)))))) 

Per chi non ha familiarità con Scheme, loop è una funzione localmente definita che si chiama in modo ricorsivo, e cond è la testa di un altro, se a catena; in questo caso, ci sono tre clausole cond, ciascuna clausola con un predicato e un conseguente, con la conseguente valutazione per la prima clausola per la quale il predicato è vero. Il predicato (zero? n) termina la ricorsione e restituisce l'elenco di output nell'ordine corretto. Il predicato (= (pq-first pq) p) indica che il capo corrente della coda di priorità è stato precedentemente emesso, quindi viene saltato ricorrendo al resto della coda di priorità dopo il primo elemento. Infine, il predicato else, che è sempre true, identifica un nuovo numero da emettere, quindi decrementa il contatore, salva il capo corrente della coda di priorità come nuovo valore precedente, aggiorna la coda di priorità per aggiungere i nuovi figli del numero corrente e inserisce il capo attuale della coda di priorità nell'output di accumulo.

Poiché non è banale per aggiornare la coda di priorità per aggiungere nuovi figli del numero corrente, tale operazione viene estratto ad una funzione separata:

(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 funzione scorre sugli elementi della ps impostare, inserendo ciascuno nella coda di priorità a sua volta; lo if restituisce la coda di priorità aggiornata, meno la sua vecchia testa, quando l'elenco ps è esaurito. Il passaggio ricorsivo separa la riga dell'elenco ps con cdr e inserisce il prodotto dell'intestazione della coda di priorità e il capo dell'elenco ps nella coda di priorità.

Ecco due esempi dell'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) 

È possibile eseguire il programma in http://ideone.com/sA1nn.

Answer 2

Questo algoritmo esplorare 2-dimensionale non è esatta, ma funziona per i primi 25 numeri interi, poi confonde 625 e 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

in base alla risposta del user448810, ecco una soluzione che usa heap e vettori dall'STL.
Ora, gli heap generano normalmente il valore più grande, quindi memorizziamo il negativo dei numeri come soluzione temporanea (dal 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; 
} 

uscita:

1 2 4 5 8 10 16 20 25 32 

Answer 4

rimozione di un numero e reinserendo tutti i suoi multipli (dai numeri primi nel set) in una coda di priorità è errata (nel senso della questione) - cioè produce sequenza corretta ma inefficientemente così.

È inefficiente in due modi: in primo luogo, lo sovrappone la sequenza; in secondo luogo, ogni operazione PriorityQueue comporta costi aggiuntivi (le operazioni remove_top e insert non sono in genere entrambe O (1), certamente non in qualsiasi implementazione PriorityQueue basata su elenco o struttura ad albero).

L'efficiente O (n) algoritmo mantiene puntatori indietro nella sequenza stessa in quanto viene prodotto, per trovare e aggiungere il numero successivo nella O (1). In pseudocodice:

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 

Per ogni multiplo minimo avanza suo puntatore, mentre allo stesso tempo calcolandone il successivo valore multiplo.Questo implementa troppo efficacemente un PriorityQueue ma con distinzioni cruciali: è prima del il punto finale, non dopo; non crea alcuna memoria aggiuntiva tranne la sequenza stessa; e la sua dimensione è costante (solo k numeri, per k numeri primi) mentre la dimensione del PriorityQueue passato aumenta quando si progredisce lungo la sequenza (nel caso della sequenza Hamming, in base al set di numeri primi, come n ^2/3, per n numeri della sequenza).

---

Il classico Hamming sequence in Haskell è essenzialmente lo stesso 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 

Possiamo generare le smooth numbers per arbitrarie primi di base utilizzando la funzione foldi (vedi Wikipedia) per ripiegare elenchi in un albero-like moda per l'efficienza, creando un albero di paragoni di dimensioni fisse:

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 

---

È anche possibile calcolare direttamente una fetta sequenza Hamming attorno al suo n esimo in O (n ^2/3) tempo, per enumerazione diretta di triplicare e valutare i loro valori attraverso i logaritmi, logval(i,j,k) = i*log 2+j*log 3+k*log 5. Questo Ideone.com test entry calcola 1 billionth Hamming number in 1.12 0,05 secondi _{(2016/08/18: speedup principale causa di utilizzo di Int posto di predefinito Integer ove possibile, anche a 32 bit; ulteriore 20% grazie al ritocco suggerite dalla @GordonBGood, portando la complessità della dimensione della banda a O (n ^1/3)).}

Questo è discusso un po 'più in this answer dove troviamo anche la sua piena attribuzione:

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 

Questo può essere generalizzato per k base di numeri primi e, probabilmente, in esecuzione in O (n ^{(k -1)/k}) tempo.

---

vedere this SO entry per un importante sviluppo successivo. inoltre, this answer è interessante. e un altro related answer.