По мотивам пары недавних статей на хабре. (Ну и для тех, кто не читал эти статьи, тем более может быть интересно — размять голову).
Постановка задачи:
1. d-ричный палиндром — это число, чьё d-ричное представление без ведущих нулей является, внезапно, палиндромом. Например, 12321 и 123321 — палиндромы, 12321000 — не палиндром.
2. Двоично-десятичный палиндром — число, являющееся и двоичным, и десятичным палиндромом.
0. Считать 0 палиндромом или нет — дело вкуса.
Задача: найти n-ный двоично-десятичный палиндром.
Брутфорс
def is_palindrom_str(s):
return s == s[::-1]
def is_decimal_palindrom(x):
return is_palindrom(dec(x))
def is_binary_palindrom(x):
return is_palindrom(bin(x)[2:]) # '0b.....'def is_bindec_palindrom(x):
return is_decimal_palindrom(x) and is_binary_palindrom(x)
def nth_bindec_palindrom(n):
k = 0
x = 0
while True:
if is_bindec_palindrom(x):
if k == n:
return x
k += 1
x += 1
# можно в одну строкуreturn next(itertools.islice(itertools.ifilter(is_bindec_palindrom, itertools.count(0)), n,None))
Здравствуйте, Кодт, Вы писали:
К>По мотивам пары недавних статей на хабре. (Ну и для тех, кто не читал эти статьи, тем более может быть интересно — размять голову).
К>Предложите наиболее быстрый способ.
Как-то нет сейчас времени особо подумать, но первое, что можно сделать — это перебирать половинки (n/2 цифр для четной длины, n/2+1 для нечетной) 10-палиндромов, зеркально отражать, а потом проверять на 2-палиндром. Во всяком случае по сравнению с тупым брутфорсом — это существенно быстрее. Потом я бы попробовал сгенерировать эти 2-10-палиндромы и посмотреть на них
Здравствуйте, _DAle_, Вы писали:
_DA>Как-то нет сейчас времени особо подумать, но первое, что можно сделать — это перебирать половинки (n/2 цифр для четной длины, n/2+1 для нечетной) 10-палиндромов, зеркально отражать, а потом проверять на 2-палиндром. Во всяком случае по сравнению с тупым брутфорсом — это существенно быстрее. Потом я бы попробовал сгенерировать эти 2-10-палиндромы и посмотреть на них
O(P^(1/2)) против O(P), конечно. (Где P — значение n-ного палиндрома).
Причём генерировать палиндром из половинки можно двумя способами:
— разложением каждого получисла на разряды (задействуя деление)
— формируя последовательность палиндромов как сложение арифметических прогрессий (задействуя только сложение)
А вот как генерировать сразу 2-10-палиндром, это интересный вопрос.
Здравствуйте, Кодт, Вы писали:
К>Причём генерировать палиндром из половинки можно двумя способами: К>- разложением каждого получисла на разряды (задействуя деление) К>- формируя последовательность палиндромов как сложение арифметических прогрессий (задействуя только сложение)
Ну, самый, имхо, простой способ — это работать просто с массивом разрядов, единственное, что в двоичное представление будет дольше перевести. А с помощью арифметических прогрессий — это как?
Здравствуйте, Кодт, Вы писали:
К>Предложите наиболее быстрый способ.
Во первых, палиндром должен быть нечётным.
Во-вторых, перечислять десятичные палиндромы быстрее, их меньше. По сути в обычном порядке мы должны делать инкремент первой половины, а вторую половину палиндрома можно получать зеркально. Например,
12321, какой следующий? Первая половина 123, добавляем единицу получаем 124, строим палиндром 12421. Таким образом мы будем быстро получать десятичные палиндромы в порядке возрастания: 12521, 12621, 12721, 12821, 12921, 13031, 13131, ...
В-третьих, с учётом во-первых, если старший равен четному числу, то его надо увеличить его ещё на единицу. Если получили 20002, то переходим на 30003.
Осталось только проверить, будет ли палиндром двоичным? Как-то так:
Если 1 или 11, то палиндром (оптимизация).
Обнулить нулевой бит (одна команда)
Получить индекс самого старшего бита (одна машинная инструкция) и обнулить его.
Если получили нуль, то палиндром.
Получить индекс самого младшего установленного бита.
Вычислить индекс бита, который должен быть самым старшим установленным. Например, Если самый старший установленный бит был 12, а новый самый младший 3, то старший будет 9
Далее, проверить, что все биты, старше девятого, установлены в нуль, например, при помощи OR. Если проверка зафейлилась, то не палиндром.
Сдвинуть число вправо на 3 и goto на начало.
Здравствуйте, Кодт, Вы писали:
К>По мотивам пары недавних статей на хабре. (Ну и для тех, кто не читал эти статьи, тем более может быть интересно — размять голову).
К>Постановка задачи:
К>1. d-ричный палиндром — это число, чьё d-ричное представление без ведущих нулей является, внезапно, палиндромом. Например, 12321 и 123321 — палиндромы, 12321000 — не палиндром. К>2. Двоично-десятичный палиндром — число, являющееся и двоичным, и десятичным палиндромом. К>0. Считать 0 палиндромом или нет — дело вкуса.
К>Задача: найти n-ный двоично-десятичный палиндром.
А число таких палиндромов не конечно?
Вероятность, что число P является десятичным палиндромом, убывает с ростом P : ~O( P^(-1/2) ).
Аналогично для двоичных палиндромов. Т.е. произведение вероятностей порядка ~O( P^-1 ).
Т.е. для любого разумного ограничения на длину палиндрома, получим не очень большое ограничение по порядковому номеру.
Затабулировать их и все.
Здравствуйте, _DAle_, Вы писали:
_DA>Ну, самый, имхо, простой способ — это работать просто с массивом разрядов, единственное, что в двоичное представление будет дольше перевести. А с помощью арифметических прогрессий — это как?
Здравствуйте, Кодт, Вы писали:
К>Схема довольно мутная, не берусь её с разбегу формализовать, — но регулярная.
Все очень просто:
Рассмотрим разложение 4-значного палиндром в 10-тичной системе на цифры (d — цифры):
-----------
N = d0 d1 d1 d0
Значение N = d0*1000 + d1*100 + d1*10 + d0*1 = d0*(1000+1) + d1*(100+10) = d0*1001 + d1*110
Теперь подставляя в выражение N = d0*1001 + d1*110 конкретные значения d0 и d1 получаем ВСЕ 4-значные палиндромы
Общая формула для палиндромов четной длины L:
SUM {dk * (10k + 10L-1-k)}, где k = [0, (L-2)/2]
Для палиндромов НЕчетной длины L:
d(L-1)/2*10(L-1)/2 + SUM {dk * (10k + 10L-1-k)}, где k = [0, (L-3)/2]
Формула верна и для двоичных палиндромов, только основание сменить с 10 на 2.
Далее можно даже составить уравнение в целых числах, которое описывает все искомые палиндромы.
Здравствуйте, Кодт, Вы писали: К>Предложите наиболее быстрый способ.
1. Формируем список десятичных палиндромов
2. Формируем список двоичных палиндромов
3. Мержим оба списка
4. Просматриваем объединенный список на повторы. Каждый повтор — искомый палиндром
Для простоты разделить п.1 (да и п.2):
а) сформировать палиндромы четной длины
б) сформировать палиндромы нечетной длины
в) смержить оба списка
Так получается проще
Главное, не проверять на палиндромность, а сразу формировать палиндромы.
Это возможно, применяя только сложение (обсуждалось выше)
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Кодт, Вы писали:
К>>Предложите наиболее быстрый способ.
Б>1. Формируем список десятичных палиндромов Б>2. Формируем список двоичных палиндромов Б>3. Мержим оба списка Б>4. Просматриваем объединенный список на повторы. Каждый повтор — искомый палиндром
Б>Для простоты разделить п.1 (да и п.2): Б>а) сформировать палиндромы четной длины Б>б) сформировать палиндромы нечетной длины Б>в) смержить оба списка Б>Так получается проще
На Haskell получилось лучше, чем на Python
Скорость в три раза выше. И главное, ближе к описанию алгоритма
type Digits = [Integer]
type Radix = Integer-- объединяет два отсортированных списка
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] xs = xs
merge a@(h:first) b@(c:second)
| h <= c = h : merge first b
| h > c = c : merge a second
-- выбирает из списка элементы, которые совпадают с предыдущим элементом списка
filter_repeat xs = [a | (a,b) <- zip xs (drop 1 xs), a == b]
-- числа представляем как список цифр в системе radix
-- младшая цифра находится в начале списка
-- получение следующего числа (для формирования половинок палиндромов)
increment :: Radix -> Digits -> Digits
increment radix [] = [1]
increment radix (d:ds)
| d < radix-1 = (d+1:) $ ds
| otherwise = (0:) $ increment radix ds
-- на основе половинки палиндрома создаем палиндром четный длины
create_even_palindrome :: Digits -> Digits
create_even_palindrome digits = reverse digits ++ digits
-- на основе половинки палиндрома создаем палиндром нечетный длины
create_odd_palindrome :: Digits -> Digits
create_odd_palindrome digits = reverse (tail digits) ++ digits
-- палиндромы по основанию radix
palindromes :: Radix -> [Integer]
palindromes radix =
let
position_weights = iterate (radix*) 1
to_number digits = sum $ zipWith (*) digits position_weights
hs = iterate (increment radix) [1]
even_palindromes = map to_number $ map create_even_palindrome hs
odd_palindromes = map to_number $ map create_odd_palindrome hs
in
merge even_palindromes odd_palindromes
-- вывод чисел, одновременно являющимися палиндромами в двоичной и десятичной системах
main =
let
ps = filter_repeat $ merge (palindromes 2) (palindromes 10)
in
mapM_ putStrLn [ show idx ++ ": " ++ show p | (idx,p) <- zip [1..] ps ]
Здравствуйте, Кодт, Вы писали: К>По мотивам пары недавних статей на хабре. (Ну и для тех, кто не читал эти статьи, тем более может быть интересно — размять голову). К>Постановка задачи: К>1. d-ричный палиндром — это число, чьё d-ричное представление без ведущих нулей является, внезапно, палиндромом. Например, 12321 и 123321 — палиндромы, 12321000 — не палиндром. К>2. Двоично-десятичный палиндром — число, являющееся и двоичным, и десятичным палиндромом. К>0. Считать 0 палиндромом или нет — дело вкуса. К>Задача: найти n-ный двоично-десятичный палиндром. >... К>Предложите наиболее быстрый способ.
Алгоритм O( P^.5 * log(P) ), где P — значение палиндрома:
Возьмем два генератора палиндромов.
Каждый из генераторов умеет генерировать строго возрастающею последовательность палиндромом, по заданному основанию. Время генерации следующего палиндрома O( log(P) ).
Для этого в генераторе храним текущий палиндром в виде разложения на цифры из которых он состоит (верхнею половину).
Для составления числа домножаем цифы на заранее вычисленные множители и складываем.
Запаршивевшем следующий палиндром у каждого из генераторов.
Если значения не совпали, запрашиваем следующий палиндром у того генератора, который выдал меньшее число, и так, пока не совпадут.
(Аналог merge sort.)
Оптимизация:
(1)
Обращаю внимание, что мы крутим запросы следующего числа для одного генератора, пока число не превысит заданное (текущее значение другого генератора).
Это значение можно разложить обратно в цифровое представление и сразу найти следующий палиндром. Это дорого, потому что требует задействовать деление.
Я реализовал эту возможность, для генераторов, для которых возможно дешевое деление (т.е. если основание равно двум).
Это привело к замедлению работы примерно в 1.5 раза.
(2)
Если одно основание кратно другому основанию, (например, основания 2 и 10 ), то последняя(первая) цифра палиндрома по меньшему основанию равна
остатку от деления последней(первой) цифры палиндрома по большему основанию, на меньшее основание.
Но, первая/последняя цифра не может быть нулем. Таким образом, для оснований 2 и 10, первая цифра десятичного палиндрома — всегда нечетная!
Это отбрасывает половину десятичных палиндромов и ускоряет работу в 2 раза (в 1.5 раза, с учетом замедления в (1) ).
Поэтому, основание другого генератора и отбрасывают серии если они заведомо не проходят.
Проверка срабатывает после обновления n-й цифры (в цифровом представлении), и если первые n-цифр не могут быть началом палиндрома,
то делаю инкремент сразу n-й цифре, а не последней.
(3)
Если одно основание равно 2, а другое нечетное (например, основания 2 и 3 ), то палиндром в представлении по большему основанию не может содержать четное
число цифр, а "центральная" цифра всегда нечетная.
(4)
Если одно основание кратно другому основанию, (например, основания 2 и 10 , то для группы палиндромов начинающихся с одних и тех-же n цифр (в представлении
по большему основанию), содержат одни и те же последнии n фцифр (в представлении по основанию 2).
Поэтому когда обновилась n-я цифра: смотрим сколько первых цифр (в двоичном представлении) не будут меняться, для группы палиндромов, начинающихся с этих
n десятичных цифр. Для этого строим двоичное представление палиндрома, в котором n-я цифра на 1 больше, и далее битовые операции...
Если есть несколько сохраняющихся цифр в двоичном представлении, и они не спадают переставленными цифрами в хвосте, то пропускам серию палиндромов.
Оптимизация (4) самая важная, поскольку в сочетании с (1) позволяет понизить порядок сложности. (С высокой вероятностью пропускаются группы из первых 3-4 десятичных цифр.)
Здравствуйте, Chorkov, Вы писали:
C>(4) C>Если одно основание кратно другому основанию, (например, основания 2 и 10 , то для группы палиндромов начинающихся с одних и тех-же n цифр (в представлении C>по большему основанию), содержат одни и те же последнии n фцифр (в представлении по основанию 2). C>Поэтому когда обновилась n-я цифра: смотрим сколько первых цифр (в двоичном представлении) не будут меняться, для группы палиндромов, начинающихся с этих C>n десятичных цифр. Для этого строим двоичное представление палиндрома, в котором n-я цифра на 1 больше, и далее битовые операции... C>Если есть несколько сохраняющихся цифр в двоичном представлении, и они не спадают переставленными цифрами в хвосте, то пропускам серию палиндромов.
Можно подробнее про эту оптимизацию? Сходу что-то не понял как работает
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Chorkov, Вы писали:
C>>(4) C>>Если одно основание кратно другому основанию, (например, основания 2 и 10 , то для группы палиндромов начинающихся с одних и тех-же n цифр (в представлении C>>по большему основанию), содержат одни и те же последнии n фцифр (в представлении по основанию 2). C>>Поэтому когда обновилась n-я цифра: смотрим сколько первых цифр (в двоичном представлении) не будут меняться, для группы палиндромов, начинающихся с этих C>>n десятичных цифр. Для этого строим двоичное представление палиндрома, в котором n-я цифра на 1 больше, и далее битовые операции... C>>Если есть несколько сохраняющихся цифр в двоичном представлении, и они не спадают переставленными цифрами в хвосте, то пропускам серию палиндромов.
Б>Можно подробнее про эту оптимизацию? Сходу что-то не понял как работает
Рассмотрим серию палиндромов начиная с 12340000004321 по 12349999994321 включительно.
Они все заканчиваются на 4321, поэтому двоичные палиндромы этой серии будут заканчиваться на 4321%(2^4) = 0001(bin).
(Более старшие разряды не будут оказывать влияния на младшие разряды двоичного представления, поскольку (10^4)%(2^4)==0. )
С другой стороны
12340000004321 = 10110011100100100001010100010001100011100001 (bin)
12349999994321 = 10110011101101110101010111001101010111010001 (bin)
Т.е. все палиндромы серии начинаются с 1011001110.....
(Сколько именно цифр двоичного представления будет совпадать заранее сказать нельзя. Проще посчитать двоичное представление начала и конца серии.)
Но двоичные палиндромы не могут начинаться на 1011... и заканчиваться на ...0001.
Значит в серии с 12340000004321 по 12349999994321 нет двоично-десятичных палиндромов.
Можно сразу переходить к 12350000005321.
Рассмотрим серию с 12350000005321 по 12369999996321 ...
1) исправил условие проверки возможности пропустить серию.
2) исправил функцию переворачивающею последовательность бит (в двоичном представлении).
Раньше проверялось только 7 бит, потому что длинна таблицы была ограничена.
Новое время перебора всех 64-битных палиндромов 11.371s.
Наблюдаемый порядок O( P ^ 0.32 ).
Перекуём баги на фичи!
