Алгоритм поиска произведений из набора простых чисел, по порядку, большему, чем х
Рассмотрим конечное множество {2,3,5,...,n}. Я интересуюсь простыми числами, но вопрос может относиться к любому набору чисел. Я хочу найти все возможные произведения этих чисел в возрастающем порядке, в частности, больше или равно некоторому числу х. Кто-нибудь знает хороший алгоритм для этого?
РЕДАКТИРОВАТЬ, чтобы уточнить:
Каждый фактор во входном наборе может использоваться любое количество раз. Если бы входные данные были {2,3,5,7}, выходными были бы {2,3,4,5,6,7,8,9,10,12,14,15,16,18,...}, Алгоритм может остановиться, как только он выдаст результат, больший или равный некоторому числу x.
7 ответов
Код Haskell, как видно из этого ответа,
hamm :: [Integer] -> [Integer]
hamm [] = []
hamm (p:ps) = xs -- e.g. hamm [2,3,5]
where xs = merge (hamm ps) -- H({p} ∪ ps) = S,
(p : map (p*) xs) -- S ⊇ {p} ∪ H(ps) ∪ { p*x | x ∊ S }
merge a@(x:xs) b@(y:ys) | x < y = x : merge xs b
| otherwise = y : merge a ys
merge [] b = b
merge a [] = a
merge Здесь мы не пытаемся устранить кратные, потому что их не будет, но только в том случае, если вы используете только простые числа во входных данных:
~> take 20 $ hamm [2,3,5,7]
[2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28]
Если нет, вам нужно использовать union вместо,
union a@(x:xs) b@(y:ys) | x < y = x : union xs b
| x > y = y : union a ys
| otherwise = x : union xs ys
union [] b = b
union a [] = a
Начиная с (выше) данного значения может быть интересной задачей. Непосредственно генерирующий срез код в нижней части этого ответа может быть взят за отправную точку.
В общем, легко пропустить упорядоченную последовательность, пока значение не будет передано. В Haskell это делается с помощью встроенного dropWhile (< n),
~> take 10 $ dropWhile (< 100) $ hamm [2,3,5,7]
[100,105,108,112,120,125,126,128,135,140]
(Изменить: заставил производить все продукты в порядке возрастания; пусть пользователи фильтруют их по своему желанию. Это обобщенная проблема чисел Хэмминга)
genHamming :: Integral a => [a] -> [a]
genHamming zs = hmng where
hmng = 1 : foldr (||) [] [map (z*) hmng | z <- zs]
[] || ys = ys
xs || [] = xs
(x:xs) || (y:ys) | x==y = x : (xs || ys)
| x<y = x : (xs || (y:ys))
| y<x = y : (ys || (x:xs))
Пример использования
Prelude Hamming> take 10 $ dropWhile (< 1000) $ genHamming [2,3,5]
[1000,1024,1080,1125,1152,1200,1215,1250,1280,1296]
Prelude Hamming>
Каждое целое число, большее 1, является продуктом "набора простых чисел", потому что оно является продуктом его основных факторов. Возможно, было бы легче начать с желаемого минимального числа и вычеркнуть все числа, которые имеют простой фактор, не входящий в ваш начальный набор. Продолжайте процесс, пока ваш набор результатов не станет достаточно большим. По сути, вы делаете модифицированное Сито Эратосфена, удаляя все кратные простых чисел, не входящих в ваш начальный набор.
Поскольку наше приложение написано на python, я предложил следующую реализацию, которой я хотел бы поделиться:
def powers(x):
y = x
while True:
yield y
y *= x
def products(factors):
y0 = factors[0]
if len(factors) == 1:
yield from powers(y0)
else:
yield y0
g1 = products(factors)
y1 = y0 * next(g1)
g2 = products(factors[1:])
y2 = next(g2)
while True:
if y1 < y2:
yield y1
y1 = y0 * next(g1)
else:
yield y2
y2 = next(g2)
if __name__ == "__main__":
import itertools
for n in itertools.islice(products([2, 3, 5, 7]), 10**6):
print(n)
Без сомнения, использование рекурсии с генераторами может быть улучшено, но на практике производительность достаточно хороша для нашего приложения. Кроме того, я все еще интересуюсь тем, как эффективно начать с заданного минимального значения, как упоминалось в ответе Уилла Несса. Спасибо всем, кто внес свой вклад.
Возможно, вы также захотите включить 2^0 * 3^0 * 5^0 * 7^0 = 1 в ваш вывод.
Способ сделать это с помощью приоритетной очереди. Если k в последовательности, то 2k, 3k, 5k и 7k. Начните вывод с 1, затем добавьте 2, 3, 5 и 7 в очередь с приоритетами. Извлеките 2 из верхней части очереди и добавьте 2*2=4, 2*3=6, 2*5=10 и 2*7=14 в очередь; очередь в этой точке будет содержать 3, 4, 5, 6, 7, 10 и 14. Вставьте 3 из верхней части очереди и добавьте 3*2=6, 3*3=9, 3*5=15 и 3*7=21 в очередь. И так далее.
Вы обнаружите, что многие элементы дублируются; например, мы добавили 6 в очередь приоритетов дважды в примере выше. Вы можете либо добавить дубликаты, и проверять каждый раз, когда вы извлекаете очередь, совпадает ли элемент с предыдущим членом последовательности, или вы можете хранить отдельный список элементов в очереди и в первую очередь воздерживаться от добавления дубликатов.
Я обсуждаю приоритетную очередь, которая содержит только отдельные элементы в моем блоге.
Поскольку каждому простому фактору разрешено появляться много раз, последовательность бесконечна. Поэтому мы не можем генерировать все продукты, а затем сортировать их. Мы должны генерировать последовательность итеративно.
Если a является членом последовательности, то {2*a, 3*a, 5*a ... n*a} также будут членами последовательности, приходящей позже.
Итак, алгоритм, который мне приходит в голову - это иметь (отсортированный, без дубликатов) буфер следующих членов последовательности. Мы извлекаем и представляем наименьшее значение и вставляем все его кратные значения в буфер.
Поскольку сложно предсказать содержание буфера для вашего стартового номера xэтот алгоритм должен начинаться с самого начала и игнорировать результаты, пока они не достигнут x порог.
Для этого на ум приходят два алгоритма. Сначала вы можете рассчитать все возможные произведения между числами, а затем отсортировать их. Хотя это кажется наивным подходом, вы могли бы ускорить его, "запомнив" последний продукт, разделив одно число и умножив другое число на его место. Это значительно уменьшило бы количество необходимых операций, если бы при правильном порядке ваших перестановок (посмотрите на Серые коды) вы могли минимизировать общее умножение.
С другой стороны, вы могли бы вычислить наборы всех исходных чисел, набор произведений пар (из двух) исходных чисел, набор произведений из 3... и так далее. Затем вы можете отсортировать каждый отдельный набор (что не должно быть сложно, чтобы убедиться, что они почти все отсортированы), и объединить наборы вместе в один отсортированный список продуктов. Это потребовало бы большего количества операций, но в итоге привело бы к почти отсортированному списку, который может занять меньше времени для построения в целом.
Другой алгоритм - взять произведение всех интересующих простых чисел и назвать это P. Построить еще один список всех исходных простых чисел в квадрате. Теперь переберите все числа до P и проверьте, делятся ли они на любое из значений в массиве простых чисел. Если они есть, бросьте их. Если нет, то добавьте их в выходной массив. Вы можете оптимизировать это, только проверяя делимость до sqrt(i), где i - это итерация в цикле for. Это все еще, вероятно, медленнее, чем вышеописанный метод.