ここには多くの良い答えがありますが、特に、受け入れられたものを含め、これらの答えのいずれかがダイクストラの元の論文の公理2をどのように維持しているかを理解するのに苦労していました：
公理2.xがシーケンス内にある場合、2 * x、3 * x、および5*xもシーケンス内にあります。
ホワイトボードを作成した後、公理2はアルゴリズムの各反復で不変ではなく、実際にはアルゴリズム自体の目標であることが明らかになりました。各反復で、公理2の条件を復元しようとします。lastが結果シーケンスの最後の値である場合S、公理2は単純に次のように言い換えることができます。
の一部xのS場合、の次の値は、、、およびの最小値でありS、2xは
。より大きくなります。これを公理2'と呼びましょう。3x5xlast
したがって、を見つけることができれば、、、の最小値を一定時間でx計算し、それをに追加することができます。2x3x5xS
しかし、どうやって見つけるのでしょうxか？1つのアプローチは、そうではありません。代わりに、に新しい要素を追加するたびに、、、、eおよびをS計算2eし、それらを最小優先度キューに追加します。この操作はにあることを保証するので、PQの最上位要素を抽出するだけで公理2'を満たします。3e5eeS
このアプローチは機能しますが、問題は、最終的に使用しない可能性のある多数の数値を生成することです。例については、この回答を参照してください。ユーザーがS（5）の5番目の要素が必要な場合、その時点でのPQは保持されます6 6 8 9 10 10 12 15 15 20 25。このスペースを無駄にできませんか？
結局のところ、私たちはもっとうまくやることができます。これらすべての数値を格納する代わりに、倍数ごとに3つのカウンター、つまり、、、およびを維持する2iだけ3jです5k。これらは、の次の番号の候補ですS。それらの1つを選択すると、対応するカウンターのみがインクリメントされ、他の2つはインクリメントされません。そうすることで、すべての倍数を熱心に生成するのではなく、最初のアプローチでスペースの問題を解決します。
n = 8のドライラン、つまり数を見てみましょう9。1ダイクストラの論文の公理1で述べられているように、私たちはから始めます。
+---------+---+---+---+----+----+----+-------------------+
| # | i | j | k | 2i | 3j | 5k | S |
+---------+---+---+---+----+----+----+-------------------+
| initial | 1 | 1 | 1 | 2 | 3 | 5 | {1} |
+---------+---+---+---+----+----+----+-------------------+
| 1 | 1 | 1 | 1 | 2 | 3 | 5 | {1,2} |
+---------+---+---+---+----+----+----+-------------------+
| 2 | 2 | 1 | 1 | 4 | 3 | 5 | {1,2,3} |
+---------+---+---+---+----+----+----+-------------------+
| 3 | 2 | 2 | 1 | 4 | 6 | 5 | {1,2,3,4} |
+---------+---+---+---+----+----+----+-------------------+
| 4 | 3 | 2 | 1 | 6 | 6 | 5 | {1,2,3,4,5} |
+---------+---+---+---+----+----+----+-------------------+
| 5 | 3 | 2 | 2 | 6 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 6 | 4 | 2 | 2 | 8 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 7 | 4 | 3 | 2 | 8 | 9 | 10 | {1,2,3,4,5,6,8} |
+---------+---+---+---+----+----+----+-------------------+
| 8 | 5 | 3 | 2 | 10 | 9 | 10 | {1,2,3,4,5,6,8,9} |
+---------+---+---+---+----+----+----+-------------------+
最小候補がすでに追加されているSため、反復6では成長しなかったことに注意してください。6前の要素をすべて覚えておく必要があるというこの問題を回避するために、対応する倍数が最小候補に等しい場合は常にすべてのカウンターをインクリメントするようにアルゴリズムを修正します。これで、次のScala実装が実現します。
def hamming(n: Int): Seq[BigInt] = {
@tailrec
def next(x: Int, factor: Int, xs: IndexedSeq[BigInt]): Int = {
val leq = factor * xs(x) <= xs.last
if (leq) next(x + 1, factor, xs)
else x
}
@tailrec
def loop(i: Int, j: Int, k: Int, xs: IndexedSeq[BigInt]): IndexedSeq[BigInt] = {
if (xs.size < n) {
val a = next(i, 2, xs)
val b = next(j, 3, xs)
val c = next(k, 5, xs)
val m = Seq(2 * xs(a), 3 * xs(b), 5 * xs(c)).min
val x = a + (if (2 * xs(a) == m) 1 else 0)
val y = b + (if (3 * xs(b) == m) 1 else 0)
val z = c + (if (5 * xs(c) == m) 1 else 0)
loop(x, y, z, xs :+ m)
} else xs
}
loop(0, 0, 0, IndexedSeq(BigInt(1)))
}