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

11

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

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

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

Проверьте этоrelated question, Принятый ответ дает O (n) Python-код, аналогичный моему ответу, который можно адаптировать к произвольным «основам». (набор простых чисел). Will Ness
Лучше спросить об этом на math.stackexchange.com Pushpak Dagade
@HighPerformanceMark да, но в порядке возрастания nims

Ваш Ответ

4   ответа
11

all its multiples (простыми числами в наборе) в очередь приоритетаwrong (в смысле вопроса) - то есть он производит правильную последовательность, ноinefficiently так.

Это неэффективно в двух отношениях - во-первых, этоoverproduces последовательность; во-вторых, каждая операция 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, но с решающими различиями - этоbefore конечная точка, а не после; он не создает никакого дополнительного хранилища, кроме самой последовательности; и его размер постоянен (простоk числа, дляk базовые простые числа), тогда как размер приоритета PriorityQueue растет, когда мы продвигаемся по последовательности (в случае последовательности Хэмминга, основанной на наборе3 простые числа, какn2/3, заn номера последовательности).

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

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

union [email protected](x:xs) [email protected](y:ys) = case compare x y of LT -> x : union  xs  b
                                              EQ -> x : union  xs  ys
                                              GT -> y : union  a   ys

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

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

Также можно напрямую рассчитатьslice последовательности Хэмминга вокруг егоnчлен вO(n2/3) время, путем прямого перечисления троек и оценки их значений с помощью логарифмов,logval(i,j,k) = i*log 2+j*log 3+k*log 5, этоТестовая запись Ideone.com исчисляет1 billionth Hamming number в1.12 0.05 секунд(2016-08-18: main speedup due to usage of Int instead of the default Integer where possible, even on 32-bit; additional 20% thanks to the tweak suggested by @GordonBGood, bringing band size complexity down to O(n1/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) время.

увидетьэта ТА запись для важного последующего развития. также,этот ответ Интересно. и другойсвязанный ответ.

Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededhereError: User Rate Limit Exceeded
3

вот решение, которое использует кучи и векторы из 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
Error: User Rate Limit ExceededheapifyError: User Rate Limit ExceededO(log n)Error: User Rate Limit ExceededO(n log n)Error: User Rate Limit Exceededonce shown an O(n) solutionError: User Rate Limit Exceeded400Error: User Rate Limit Exceeded80Error: User Rate Limit Exceeded200Error: User Rate Limit Exceeded400Error: User Rate Limit Exceeded500,625,640,800,1000,1250,1280,1600,500,512,640Error: User Rate Limit Exceeded
3

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

Powers of 2 and 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
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededatan( log(5)/log(2) ) * 180 / pi = 66.69958829239839Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededlog 5/log 2 = 2.321928094887362Error: User Rate Limit Exceeded
8

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

Google для "числа Хэмминга" или «обычный номер»; или перейти к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.

Error: User Rate Limit Exceeded(f '(2 3 5) N)Error: User Rate Limit Exceededlog(t2/t1) / log(n2/n1)Error: User Rate Limit Exceededt_iError: User Rate Limit Exceededn_iError: User Rate Limit Exceeded
Error: User Rate Limit Exceededempirical complexityError: User Rate Limit ExceededshouldError: User Rate Limit Exceeded(define (update lt? pq ps) (pq-merge lt? (pq-rest lt? pq) (pq-from-ordlist (map (lambda(p)(* (pq-first pq) p)) ps))))Error: User Rate Limit Exceeded(define (pq-from-ordlist xs) (cons (car xs) (map list (cdr xs)))).
Error: User Rate Limit Exceededwhich is growing in sizeError: User Rate Limit Exceededpq-rest? pq-insertError: User Rate Limit Exceededpq-restError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы