[задачка] Hamming sequence

вот пример тупого решения:


import bisect

def gen235(mults=(2,3,5)):
	l = [(1,1)]
	while l:
		i, m=l.pop(0); 
		yield i
		for n in mults:
			if n>=m:
				bisect.insort(l, (i*n, n))


(bisect.insort вставляет элемент в сортированый список)

Линейное пространство. Нипайдёт.

Тупое решение с ограниченным пространством:

divideToTheEnd m n = if n `mod` m == 0 then n `div` m else n

isHamming n = foldr divideToTheEnd n [2,3,5] == 1

hammings = [n | n <- [1..], isHamming n]

Экспоненциальное время.

Кстати, мой любимый пример на линейное пространство и время:

hammings = 1 : unfoldr (\xss -> let x = minimum $ map head xss in Just (x, map (dropWhile (x==)) xss)) (map (\n -> map (n *) hammings) [2,3,5])

Последовательность включает все простые числа?

> Последовательность включает все простые числа?

нет, последовательность включает все числа вида 2^n 3^m 5^k где n, m, k целые неотрицательные.

> divideToTheEnd m n = if n `mod` m == 0 then n `div` m else n

тут где-то рекурсия потерялась, или мне кажется?

divideToTheEnd m n = if n `mod` m == 0 then (divideToTheEnd m (n `div` m)) else n

> Последовательность включает все простые числа?

> нет, последовательность включает все числа вида 2^n 3^m 5^k где n, m, k целые неотрицательные.

потому что простое число (больше 5) является собственным делителем, а по условию задачи простых делителей кроме 2 3 5 быть не должно.

O(n)

-- Merges two infinite lists
merge :: (Ord a) => [a] -> [a] -> [a]
merge (x:xs)(y:ys)
  | x == y    = x : merge xs ys
  | x <  y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys
 -- Lazily produce the hamming sequence
hamming :: [Integer]
hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))

> O(n)

O(n) время или память?

> Линейное пространство. Нипайдёт.

вообще говоря не ясно, линейное ли -- на каждый pop() приходится
один или более insort(), так что в принципе может быть полиномиальное
и даже экспоненциальное.

> Тупое решение с ограниченным пространством:
> ...
> Экспоненциальное время.

так вот вопрос в том, какой минимальной пространственной сложности
можно достичь, сохраняя линейное время.

можно ли доказать, что с ограниченным пространством линейного
времени достичь невозножно?

> hammings = 1 : unfoldr (\xss -> let x = minimum $ map head xss in Just (x, map (dropWhile (x==)) xss)) (map (\n -> map (n *) hammings) [2,3,5])

Перл тихо плачет в сторонке.

Да, спасибо. Потерял.