私は素数のセットを持っており、それらの素因数のみを昇順で使用して整数を生成する必要があります。
たとえば、セットがp = {2、5}の場合、整数は1、2、4、5、8、10、16、20、25、…</p>になります。
この問題を解決するための効率的なアルゴリズムはありますか？
質問する
5926 次
4 に答える
13
数値を削除し、そのすべての倍数を（セット内の素数によって）優先キューに再挿入することは（質問の意味で）間違っています-つまり、正しいシーケンスを生成しますが、非効率的です。
これは2つの点で非効率的です。1つは、シーケンスを過剰に生成することです。第2に、各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
関数（ウィキペディアを参照）を使用して任意の素数の滑らかな数を生成し、効率を上げるためにリストをツリーのように折りたたんで、固定サイズの比較ツリーを作成できます。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ビットでも、可能な場合はデフォルトの代わりに使用することによる主な高速化。 @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
これは、おそらくO（n （k-1）/ k）時間で実行されるk個の素数に対しても一般化できます。
重要な後の開発については、このSOエントリを参照してください。また、この答えは興味深いものです。および別の関連する回答。
于 2012-04-15T06:32:54.937 に答える
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は2つのパラメーターを取ります。1つはセットps内の数値のリストで、もう1つは出力の先頭から出力する項目の数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チェーンの先頭です。この場合、3つの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ます。
アルゴリズムの2つの例を次に示します。
> (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
この2次元探索アルゴリズムは正確ではありませんが、最初の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 に答える
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 に答える