Генерация целых чисел в порядке возрастания с использованием набора простых чисел
У меня есть набор простых чисел, и я должен генерировать целые числа, используя только эти простые факторы в порядке возрастания.
Например, если набор равен p = {2, 5}, то мои целые числа должны быть 1, 2, 4, 5, 8, 10, 16, 20, 25, …
Есть ли эффективный алгоритм для решения этой проблемы?
4 ответа
Основная идея состоит в том, что 1 является членом набора, и для каждого члена набора n также 2 n и 5 n являются членами набора. Таким образом, вы начинаете с вывода 1 и помещаете 2 и 5 в очередь с приоритетами. Затем вы несколько раз выталкиваете передний элемент очереди приоритетов, выводите его, если он отличается от предыдущего вывода, и помещаете число 2 и 5 раз в очередь приоритетов.
Чтобы узнать больше, найдите "номер Хэмминга" или "обычный номер" или перейдите к A003592.
----- ДОБАВЛЕНО ПОЗЖЕ -----
Я решил потратить несколько минут на обеденный перерыв, чтобы написать программу для реализации алгоритма, описанного выше, с использованием языка программирования Scheme. Во-первых, вот библиотека реализации приоритетных очередей с использованием алгоритма кучи сопряжения:
(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 ((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))))))
Для тех, кто не знаком со Схемой, loop является локально определенной функцией, которая вызывается рекурсивно, и cond является главой цепочки if-else; в этом случае есть три cond пункты, каждое предложение с предикатом и последующим, с последующим вычислением для первого предложения, для которого предикат является истинным. Предикат (zero? n) завершает рекурсию и возвращает список вывода в правильном порядке. Предикат (= (pq-first pq) p) указывает на то, что текущий заголовок приоритетной очереди был выведен ранее, поэтому он пропускается путем повторения с остальной частью приоритетной очереди после первого элемента. Наконец, else Предикат, который всегда имеет значение true, идентифицирует новый номер для вывода, поэтому он уменьшает счетчик, сохраняет текущий заголовок очереди с приоритетами как новое предыдущее значение, обновляет очередь с приоритетами, чтобы добавить новых потомков текущего номера, и вставляет текущий заголовок приоритетной очереди в накопительный вывод.
Поскольку обновление очереди приоритета нетривиально, чтобы добавить новых дочерних элементов текущего номера, эта операция извлекается в отдельную функцию:
(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 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
Мы можем генерировать гладкие числа для произвольных базовых простых чисел, используя 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 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
Также возможно непосредственно вычислить срез последовательности Хемминга вокруг его n- го члена за время O (n 2/3) путем прямого перечисления троек и оценки их значений с помощью логарифмов, 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 для важного последующего развития. Кроме того, этот ответ интересен. и другой связанный ответ.
Этот алгоритм двумерного исследования не является точным, но работает для первых 25 целых чисел, а затем смешивает 625 и 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
Основываясь на ответе пользователя user448810, вот решение, которое использует кучи и векторы из STL.
Теперь кучи обычно выводят наибольшее значение, поэтому мы храним отрицательные числа в качестве обходного пути (так как 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;
}
Выход:
1 2 4 5 8 10 16 20 25 32