Здесь много хороших ответов, но мне было трудно понять их, в частности, как любой из этих ответов, включая принятый, поддерживал аксиому 2 в оригинальной статье Дейкстры :
Аксиома 2. Если x находится в последовательности, то есть 2 * x, 3 * x и 5 * x.
После некоторой доски стало ясно, что аксиома 2 не инвариант на каждой итерации алгоритма, а фактически цель самого алгоритма.На каждой итерации мы пытаемся восстановить условие в аксиоме 2. Если last является последним значением в последовательности результатов S, аксиома 2 может быть просто перефразирована как:
Для некоторых x в S, следующее значение в S - это минимум 2x, 3x и 5x, который больше last.Давайте назовем эту аксиому 2 '.
Таким образом, если мы можем найти x, мы можем вычислить минимум 2x, 3x и 5x в постоянном времени и добавитьэто к S.
Но как нам найти x?Один подход, мы не делаем;вместо этого, всякий раз, когда мы добавляем новый элемент e в S, мы вычисляем 2e, 3e и 5e и добавляем их в очередь с минимальным приоритетом.Поскольку эта операция гарантирует, что e находится в S, простое извлечение верхнего элемента PQ удовлетворяет аксиоме 2 '.
Этот подход работает, но проблема в том, что мы генерируем группу чисел, которые мы не можемв конечном итоге с помощью.См. этот ответ для примера;если пользователь хочет 5-й элемент в S (5), PQ в этот момент удерживает 6 6 8 9 10 10 12 15 15 20 25.Разве мы не можем тратить это пространство впустую?
Оказывается, мы можем добиться большего.Вместо того, чтобы хранить все эти числа, мы просто поддерживаем три счетчика для каждого из кратных, а именно, 2i, 3j и 5k.Это кандидаты на следующий номер в S.Когда мы выбираем один из них, мы увеличиваем только соответствующий счетчик, а не два других.Поступая так, мы не с готовностью генерируем все кратные числа, таким образом решая проблему с пространством при первом подходе.
Давайте посмотрим пробный прогон для 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)))
}