nim*_*ims 11 algorithm primes hamming-numbers smooth-numbers
我有一组素数,我必须使用递增顺序的那些素因子生成整数.
例如,如果集合是p = {2,5}那么我的整数应该是1,2,4,5,8,10,16,20,25 ......
有没有有效的算法来解决这个问题？
Wil*_*ess 11
删除一个数字并将其所有的倍数(通过集合中的素数)重新插入到优先级队列中是错误的(在问题的意义上) - 即它产生正确的序列但效率低下.
它在两个方面效率低下 - 首先,它过度生成序列; 第二,每个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个基本素数),而过去的优先级Q1的大小随着我们沿着序列前进而增长(在汉明序列的情况下,基于3个素数的集合,作为n 2/3,对于n个序列).
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
也可以通过直接枚举三元组并通过对数评估它们的值,在O(n 2/3)时间内直接计算其第n个成员周围的汉明序列切片.这个Ideone.com测试条目在1.12 0.05秒内计算出第十亿个汉明数字(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)时间内运行.
请参阅此SO条目以获得重要的后续开发.此外,这个答案很有趣.和另一个相关的答案.
基本思想是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谓词始终为true,标识要输出的新数字,因此它递减计数器,将优先级队列的当前头保存为新的先前值,更新优先级队列以添加当前的新子项number,并将优先级队列的当前头插入累积输出.
由于更新优先级队列以添加当前号码的新子节点非常简单,因此将该操作提取到单独的函数:
(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上运行该程序.