Генерация целых чисел в порядке возрастания с использованием набора простых чисел

У меня есть набор простых чисел, и я должен генерировать целые числа, используя только эти простые множители в порядке возрастания.

Например, если множество p = {2, 5}, то мои целые числа должны быть 1, 2, 4, 5, 8, 10, 16, 20, 25, …

Есть ли эффективный алгоритм для решения этой проблемы?

Основная идея состоит в том, что 1 является членом множества, и для каждого члена множества n, так что 2 n и 5 n являются членами множества. Таким образом, вы начинаете с вывода 1 и нажимаете 2 и 5 в очередь приоритетов. Затем вы повторно добавляете передний элемент очереди приоритета, выводите его, если он отличается от предыдущего вывода, и нажимайте 2 раза и 5 раз число в очередь приоритета.

Google для «номера Хэмминга» или «обычного номера» или перейдите в A003592, чтобы узнать больше.

—– ДОБАВЛЕНО ПОЗЖЕ —–

Я решил потратить несколько минут на мой обед, чтобы написать программу для реализации алгоритма, описанного выше, с использованием языка программирования Схемы. Во-первых, это реализация библиотеки очередей приоритетов с использованием алгоритма спаривания кучи:

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

Теперь для алгоритма. Функция f принимает два параметра, список номеров в наборе ps и номер n элементов для вывода из заголовка вывода. Алгоритм слегка изменен; очередь приоритетов инициализируется нажатием 1, затем начинаются шаги извлечения. Переменная p – это предыдущее выходное значение (изначально 0), pq – очередь приоритетов, а xs – это выходной список, который накапливается в обратном порядке. Вот код:

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

Для тех, кто не знаком с Scheme, loop - это локально определенная функция, которая называется рекурсивно, а cond является главой цепочки if-else; в этом случае существует три условия cond , каждое предложение с предикатом и последующее, с последующей оценкой для первого предложения, для которого предикат является истинным. Предикат (zero? n) завершает рекурсию и возвращает выходной список в правильном порядке. Предикат (= (pq-first pq) p) указывает, что текущий заголовок очереди приоритетов был выведен ранее, поэтому он пропускается повторением с остальной очередью приоритета после первого элемента. Наконец, предикат else , который всегда верен, идентифицирует новый номер, который должен быть выведен, поэтому он уменьшает счетчик, сохраняет текущий заголовок очереди приоритетов в качестве нового предыдущего значения, обновляет очередь приоритетов, чтобы добавить новых детей из текущее число и вставляет текущий заголовок очереди приоритета в накопительный вывод.

Поскольку нет необходимости обновлять очередь приоритетов для добавления новых детей текущего числа, эта операция извлекается в отдельную функцию:

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

Функция перебирает элементы набора ps , вставляя их поочередно в очередь приоритетов; if возвращает обновленную очередь приоритета, минус ее старую голову, когда список ps исчерпан. Рекурсивный шаг разбивает голову списка ps на cdr и вставляет продукт главы очереди приоритета и главы списка ps в очередь приоритетов.

Вот два примера алгоритма:

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

Вы можете запустить программу по адресу http://ideone.com/sA1nn .

Удаление числа и повторное вложение всех его кратных (по простым числам) в очередь приоритетов неверно (в смысле вопроса) – то есть оно производит правильную последовательность, но неэффективно .

Он неэффективен двумя способами – во-первых, он перепроизводит последовательность; во-вторых, каждая операция PriorityQueue берет дополнительную стоимость (операции remove_top и insert обычно не являются O (1) , но, конечно же, не реализованы в реализационной программе PriorityQueue на основе списка или на основе дерева).

Эффективный алгоритм O (n) сохраняет указатели обратно в саму последовательность по мере ее создания, чтобы найти и добавить следующее число в O (1) . В псевдокоде:

  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 

Для каждого минимального множителя он продвигает свой указатель и в то же время вычисляет его следующее несколько значений. Это слишком эффективно реализует PriorityQueue, но с критическими различиями – это до конечной точки, а не после; он не создает никакого дополнительного хранилища, кроме самой последовательности; и его размер является постоянным (только k чисел, для k базовых простых чисел), тогда как размер предыстории PriorityQueue растет по мере продвижения по последовательности (в случае последовательности Хэмминга, основанной на множестве 3 простых чисел, как n 2 / 3 , для n номеров последовательности).


Классическая последовательность Хэмминга в Haskell по сути является одним и тем же алгоритмом:

 h = 1 : map (2*) h `union` map (3*) h `union` map (5*) h union [email protected](x:xs) [email protected](y:ys) = case compare xy of LT -> x : union xs b EQ -> x : union xs ys GT -> y : union a ys 

Мы можем генерировать гладкие числа для произвольных базовых простых чисел, используя функцию foldi (см. Википедию ), чтобы foldi списки по древовидной моде для эффективности, создавая дерево сравнений:

 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 

Также можно непосредственно вычислить срез последовательности Хэмминга вокруг своего n- го члена в O (n 2/3 ) времени, путем прямого enums троек и оценки их значений через логарифмы, logval(i,j,k) = i*log 2+j*log 3+k*log 5 . Эта тестовая запись Ideone.com вычисляет 1 млрд. Номеров Хэмминга за 1.12 0.05 секунд (2016-08-18: основное ускорение за счет использования Int вместо Integer по умолчанию, где это возможно, даже на 32-битных, еще 20% благодаря настройке предложенный @GordonBGood, при этом сложность размера группы до O (n 1/3 )).

Это обсуждается еще в этом ответе, где мы также находим его полную атрибуцию:

 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 

Это можно обобщить и для k базовых простых чисел, вероятно, работающих в O (n (k-1) / k ) времени.


см. эту запись SO для важной более поздней разработки. Кроме того, этот ответ интересен. и другой ответ .

Этот 2-мерный алгоритм исследования не является точным, но работает для первых 25 целых чисел, затем смешивается с 625 и 512.

Полномочия 2 и 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 

Основываясь на ответе user448810, вот решение, которое использует кучи и векторы из STL.
Теперь, кучи обычно выводят наибольшее значение, поэтому мы сохраняем отрицание чисел в качестве обходного пути (поскольку 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; } 

Вывод:

 1 2 4 5 8 10 16 20 25 32 
Давайте будем гением компьютера.