10 октября 2012 в 00:03

Диаграммы разложения на простые множители из песочницы

Недавно в свободное время написал программу для генерации диаграмм, полученных с помощью разложения числа на простые множители или "факторизационных диаграмм".

Вот так выглядит 700:


По расположению точек несложно заметить, что всего их здесь 7*5*5*2*2.

Далее описание того, как это работает.

Для начала несколько импортов: функция для разложения целого числа на простые множители и библиотека для отрисовки диаграмм.

module Factorization where

import Math.NumberTheory.Primes.Factorisation (factorise)

import Diagrams.Prelude
import Diagrams.Backend.Cairo.CmdLine

type Picture = Diagram Cairo R2


Функция primeLayout принимает целое число n (должно быть простым числом) и какое-то изображение, и затем симметрично располагает n копий изображения.

primeLayout :: Integer -> Picture -> Picture 


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

primeLayout 2 d
  | width d > height d = d === strutY (height d / 2) === d
  | otherwise          = d ||| strutX (width d / 2)  ||| d


Это значит, что если есть несколько коэффициентов, равных двум, и мы вызываем primeLayout несколько раз, получается что-то вроде:


Если бы мы всегда рисовали копии рядом друг с другом, мы бы получили

что не так красиво и наглядно.

Для других чисел, мы создаем правильный многоугольник соответствующего размера и распологаем копии по вершинам многоугольника.

primeLayout p d = decoratePath pts (repeat d)
  where pts = polygon with { polyType   = PolyRegular (fromIntegral p) r
                           , polyOrient = OrientH
                           }
        w = max (width d) (height d)
        r = w * c / sin (tau / (2 * fromIntegral p))
        c = 0.75


Например, вот primeLayout 5, примененная к зеленому квадрату:


Далее, имея список простых множителей, мы рекурсивно создаем все изображение.
Если список пуст, это соответствует цифре 1, поэтому мы просто рисуем черную точку.

factorDiagram' :: [Integer] -> Diagram Cairo R2
factorDiagram' []     = circle 1 # fc black



В ином случае если первое простое число называется p, а остальные ps, мы рекурсивно создаем изображение из остальных простых чисел ps и рисуем p копий этого изображения используя функцию primeLayout.

factorDiagram' (p:ps) = primeLayout p (factorDiagram' ps) # centerXY


И наконец, чтобы превратить число в факторизационную диаграмму, мы раскладываем его на простые множители, нормализуем их в список простых чисел, переворачиваем, чтобы большие числа были в начале и вызываем factorDiagram'.

factorDiagram :: Integer -> Diagram Cairo R2
factorDiagram = factorDiagram' 
              . reverse 
              . concatMap (uncurry $ flip replicate) 
              . factorise


И вуаля! Разумеется, это хорошо работает лишь с числами из диапазона {2, 3, 5, 7} (и возможно 11). Например, вот так выглядит 121:


А так 611:


Тут диаграммы всех целых чисел от 1 до 36:


Степени тройки особенно интересны, так как их диаграммы это треугольники Серпинского. Вот, например, 35 = 243:


Степени двойки тоже весьма неплохи, они представляют собой фракталы, называемые Канторова пыль. Вот 210 = 1024:


И напоследок 104:


Автор: Brent Yorgey. Оригинал.

P.S.: Практического применения особо нет (разве что для демонстрации разложения числа на простые множители), но выглядит забавно. :)
В конце оригинальной статьи автор говорит, что хотел бы оформить приложение в виде сайта, чтобы любой мог ввести свое число и посмотреть результат.
Я сделал нечто подобное на javascript, желающие могут поэксперементировать тут. Производительность ниже, чем у haskell версии, поэтому аккуратнее с большими числами.
P.P.S.: Пост из песочницы, поэтому заранее извиняюсь, что не оформил перевод подобающим образом.

UPD: lany написал весьма интересную статью с созданием похожего визуализатора диаграмм, но с более высокой производительностью на больших числах. Хотите посмотреть, как выглядит разложение числа 3628800? Вам сюда. :)
+83
6372
133
helarqjsc 9,9

Комментарии (15)

+2
lisyarus #
Отлично! Мне кажется, что если не только рекурсивно вызывать отрисовку, но и поворачивать к центру, то выйдет покрасивее)
НЛО прилетело и опубликовало эту надпись здесь
+6
zw0rk #
Ссылку на оригинал неплохо бы всё-таки дать. Или я слепой, тогда прошу прощения.
0
helarqjsc #
Добавил.
0
backmeupplz #
Ну вот зачем вы упомянули большие числа? Это просто вынудило меня поробовать 100000000…
Ни разу не видел настолько затормозившего и прожорливого Safari :)
+4
MKrivosheev #
> P.P.S.: Пост из песочницы, поэтому заранее извиняюсь, что не оформил перевод подобающим образом.
< Ну так напишите просто тектсом в конце «автор тот-то, ссылка вот». И карма будет чиста не только на Хабре, но и вообще по жизни :)
0
helarqjsc #
Точно. Туплю)
+2
nickme #
Красиво! Пифагор бы порадовался :)
+1
nickme #
С числом 210 смешно получается (или с 222, короче, если в делителях только одна двойка) — эффект двоения в глазах зачетный :)
+2
ivanra #
Как вариант, можно было бы все квадраты простых чисел рисовать квадратами, по аналогии в 2x2
+1
k06a #
Что-то я так и не дождался факторизации числа 3628800 (10!)
+1
lany #
–1
rafuck #
Или я чего-то не понимаю, или у вас вместо 700 получается 600 (6 групп внутри 5 звездочек по 5 квадратов по 4 точки в каждом)
0
rafuck #
упс, окосоглазел, 7 групп, все верно
0
macik_spb #
«А как быть с простыми числами?» — подумал я —
«Ну ладно, попробуем случайное число, пусть будет 761».

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.