我有一组素数，我必须只使用这些素数以递增的顺序生成整数。
例如，如果集合是p = {2, 5}，那么我的整数应该是 1, 2, 4, 5, 8, 10, 16, 20, 25, ...</p>
有没有有效的算法来解决这个问题？
问问题
5926 次
4 回答
13
删除一个数字并将其所有倍数（通过集合中的素数）重新插入优先级队列是错误的（在问题的意义上） - 即它产生正确的序列但效率低下。
它在两个方面效率低下 - 首先，它过度生产了序列；其次，每个 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 ref (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
我们可以使用函数（参见Wikipedia）以树状方式折叠列表以提高效率，从而为任意基本素数生成平滑数，从而创建固定大小的比较树：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
也可以通过直接枚举三元组并通过对数评估它们的值，在O(n 2/3 )时间内直接计算围绕其第n个成员的汉明序列切片。这个Ideone.com 测试条目在1.12 0.05秒内计算了第 10 亿个汉明数（2016-08-18：主要加速由于尽可能使用而不是默认值，即使在 32 位上也是如此；由于建议的调整，额外的 20% @GordonBGood，将波段大小复杂度降低到 O(n 1/3 ))。logval(i,j,k) = i*log 2+j*log 3+k*log 5IntInteger
在这个答案中对此进行了更多讨论，我们还找到了它的完整归属：
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 )时间内运行。
于 2012-04-15T06:32:54.937 回答
8
基本思想是 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))))))
对于那些不熟悉 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运行该程序。
于 2012-04-12T15:12:44.267 回答
3
根据 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
于 2012-04-12T15:50:47.970 回答
3
这种二维探索算法并不精确，但适用于前 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
于 2012-04-12T15:34:24.093 回答