А это n-мерное пространство сейчас с нами в одной комнате?
Это математическая абстракция. Декарт в свое время придумал декартовы координаты как способ работы с алгебраическими уравнениями на геометрической плоскости. До Декарта вот этих осей абсцисс и ординат не было, и у точек координат тоже не было. Оказалось удобно. А потом понеслось... а если в уравнении переменных не 2, а 3? а если вообще n?
Лучше всего для психического здоровья работать с n-мерным пространством как с набором точек, у которых n координат. Представлять себе только 3-мерное пространство, про n-мерное думать "ну там наверно всё выглядит примерно аналогично".
Если герой этой статьи на Хабре нашел как запихать много сфер в n-мерное пространство, думаю, несложно будет адаптировать его находку к тому, чтобы запихать много "шапочек" на n-мерную сферу.
Ну как, 1 байт - это точка в 8-мерном пространстве, а именно вершина 8-мерного единичного гиперкуба. Машинное 32-битное слово aka int в C++ - точка в 32-мерном пространстве. Блоки бит корректировать эффективнее, чем каждый бит по-отдельности. Например, кодом Хэмминга.
Коды коррекции ошибок такие - "ну да, ну да, пошли мы нафиг". Всем же известно, что упаковка сфер полезна только с трёхмерном пространстве - арбузы на рынке в пирамидки складывать. А то, что, скажем, плотность передачи данных по вайфаю можно будет раз в 100 увеличить - это никому не нужно.
Это вопрос к Хабру, наверно. У меня формулы внутри текста в разных браузерах вообще везде разные: в Edge непомерно большие, в Яндекс-браузере на телефоне непомерно маленькие. При всём при этом в режиме редактирования статьи размеры формул везде идеально как надо.
У меня задача получилась эквивалентная такой. На примере тернарного случая: нужно посчитать количество способов расставить в кубе 3х3х3 числа от 1 до 3 так, чтобы в каждом ряду (из 3х элементов), параллельному оси x, была ровно одна единица, в каждом ряду, параллельному оси y, была ровно одна двойка, и в каждом ряду, параллельному оси z, была ровно одна тройка. Для кватернарного случая это будет уже гиперкуб 4х4х4х4, числа от 1 до 4, направлений осей 4. Ну и так далее.
Вот эти ваши "дефекты" по сути кодируют положения всех единиц, где цвет - это номер слоя, в котором эти единицы располагаются. Как только мы зафиксировали положения единиц, задача распадается на X независимых - нам нужно посчитать для каждого слоя (или "гиперслоя" при X>3) количество способов расставить там остальные числа, после чего количество этих способов по всем слоям перемножить (это по сути функция Ф). Ну и ответом будем сумма способов по всем "дефектам".
Из ограничений выше следует, что в каждом гиперслое единиц должно быть поровну, иначе числа для других осей в этот гиперслой не поместятся. То есть в тернарном случае в каждом слое должно быть по 3 единицы, в кватернарном - по 16 (там гиперслои - это кубы 4х4х4). Так повезло, что для каждой расстановки трех единиц в одном слое в тернарном случае дальше способов заполнить либо 2, либо 0 (если расстановка этих трех единиц в один ряд). В кватернарном случае, боюсь, будет все сложнее, и просто умножением на степень двойки не отделаться.
Итого количество "дефектов" для кватернарного случая равно 64! / (16!)^4, что довольно много, поэтому объединять их в классы эквивалентности - хорошая идея. Но что-то классов эквивалентности тоже пока получается много)
3. В качестве представителя можно взять лексикографически максимальный по всем эквивалентным объектам. Представителей всех классов эквивалентности (а значит и сами классы) можно найти перебором с отсечениями. Просто генерируем элементы объектов в порядке учета их в лексикографическом порядке, применяем действия группы, если удалось перемешать элементы объекта так, что получился объект лексикографически больше - то окатываемся.
4. Можем. Для этого надо представить каждый элемент группы в виде последовательности базовых действий группы. Например, для куба 4х4х4: сначала вращение, потом перестановка слоев по оси x, потом по оси y, потом z. Теперь, пусть мы повращали и переставили слои по оси x. Тогда дальше у нас будут переставляться только блоки из 4 элементов. Но если множество этих блоков не совпадает с множеством блоков начального куба, то смысла их переставлять нет - там нет элементов стабилизатора.
Ну или можно глубже вникнуть в структуру группы. Например, для группы всех перестановокмощность стабилизатора для объекта(состоящего изэлементов), на который действует группа, равна произведению факториалов размеров подмножеств одинаковых элементов в.
У меня еще есть непонятки по прочитанному. Я у себя в голове немного другую модель задачи построил, она на изложенную в статье не до конца накладывается. Например, мне не до конца понятно почему для последних двух линий (двух "гиперслоев" в кватернарном случае) надо домножать на какую-то фиксированную степень двойки. У меня двойки для тернарного случая вылезают из функции Ф.
Если что, я свою модельку закодил, и она тоже дает 10752 для тернарного случая. Но наверно поля комментария будут "слишком узки", чтобы расписывать ее во всех подробностях.
Из всего, что здесь написано, интерес представляют идеи использования дробных и отрицательных чисел в некоторых местах. Но, думаю, математики уже давно додумались до применения такого в своих задачах.
Лупа и Пупа пошли получать зарплату. Лупа получил кучу денег, а Пупа — только одну купюру.
— Что случилось? — спросил я. — Один из тех несчастных случаев на производстве, — сказал он.
Я никогда не мог заставить его рассказать об этом подробнее.
Он просто сказал: «Один из тех».
Элементарное означает, что в нём используются только понятия и прочие инстументы, не выходящие за пределы школьной программы (без всяких лютых «высших» математик), хотя оно может быть довольно большим и его будет не так просто понять.
Это примерно как переписать программу без использования сторонних библиотек.
Это разные задачи. В теореме о четырёх красках граф планарный (точнее, плоский), то есть его можно нарисовать на плоскости так, чтобы ребра, изображенные в виде кривых, не пересекались. Здесь же граф единичный расстояний — т.е. рёбра могут пересекаться как угодно, главное чтобы при изображении на плоскости длины всех рёбер были равны единице.
Вспомнилось, как я году эдак в 2013 матрицы перемножал. Правда, там в ячейках были не float, а int64 (точнее, в A*B=C в A и B — инты, а в C должно было инт64 влезать). Размеры матричек 5000х5000. Подробнее о задаче на fastcomputing.org (вебархив, ибо проект ныне покойный). А вот табличка рекордов. В 40 секунд тогда упихал. Подробности реализации сейчас не вспомню, но вроде там Виноград-Штрассен, который где-то то ли на 200х200, то ли на 1000х1000 переключается уже на перемножение в лоб. Без Штрассена было тормознее, насколько помню. В перемножении в лоб тоже всякие SSE, помню разве что только один хак: мы умножаем не строчку A на строчку B (B транспонирована, конечно), а пару строчек A на пару строчек B, тем самым сокращая число чтений, потом все идет чисто на регистрах процессора, и на выходе получаем 4 значения для этих самых пар строчек.
Немного пооптимиздил:
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.
Это математическая абстракция. Декарт в свое время придумал декартовы координаты как способ работы с алгебраическими уравнениями на геометрической плоскости. До Декарта вот этих осей абсцисс и ординат не было, и у точек координат тоже не было. Оказалось удобно. А потом понеслось... а если в уравнении переменных не 2, а 3? а если вообще n?
Лучше всего для психического здоровья работать с n-мерным пространством как с набором точек, у которых n координат. Представлять себе только 3-мерное пространство, про n-мерное думать "ну там наверно всё выглядит примерно аналогично".
Если я буду подробно все расписывать - получится статья на 20 экранов)
Вот я нашел другую статью с видео на 7 минут, в которой на пальцах поясняется суть: Контактное число шаров и сферические коды / Этюды // Математические этюды
Если герой этой статьи на Хабре нашел как запихать много сфер в n-мерное пространство, думаю, несложно будет адаптировать его находку к тому, чтобы запихать много "шапочек" на n-мерную сферу.
Придумано, и много, но уже отнюдь не для начинающих Maximum flow problem - Wikipedia
Ну как, 1 байт - это точка в 8-мерном пространстве, а именно вершина 8-мерного единичного гиперкуба. Машинное 32-битное слово aka int в C++ - точка в 32-мерном пространстве. Блоки бит корректировать эффективнее, чем каждый бит по-отдельности. Например, кодом Хэмминга.
Коды коррекции ошибок такие - "ну да, ну да, пошли мы нафиг". Всем же известно, что упаковка сфер полезна только с трёхмерном пространстве - арбузы на рынке в пирамидки складывать. А то, что, скажем, плотность передачи данных по вайфаю можно будет раз в 100 увеличить - это никому не нужно.
У меня в одном браузере так (Edge)
В другом так (Firefox)
В третьем так (Яндекс на телефоне)
В режиме редактирования в Edge так
Явно с размерами формул что-то нездоровое происходит
Это вопрос к Хабру, наверно. У меня формулы внутри текста в разных браузерах вообще везде разные: в Edge непомерно большие, в Яндекс-браузере на телефоне непомерно маленькие. При всём при этом в режиме редактирования статьи размеры формул везде идеально как надо.
UPD. Написал в техподдержку, может поправят.
У меня задача получилась эквивалентная такой. На примере тернарного случая: нужно посчитать количество способов расставить в кубе 3х3х3 числа от 1 до 3 так, чтобы в каждом ряду (из 3х элементов), параллельному оси x, была ровно одна единица, в каждом ряду, параллельному оси y, была ровно одна двойка, и в каждом ряду, параллельному оси z, была ровно одна тройка. Для кватернарного случая это будет уже гиперкуб 4х4х4х4, числа от 1 до 4, направлений осей 4. Ну и так далее.
Вот эти ваши "дефекты" по сути кодируют положения всех единиц, где цвет - это номер слоя, в котором эти единицы располагаются. Как только мы зафиксировали положения единиц, задача распадается на X независимых - нам нужно посчитать для каждого слоя (или "гиперслоя" при X>3) количество способов расставить там остальные числа, после чего количество этих способов по всем слоям перемножить (это по сути функция Ф). Ну и ответом будем сумма способов по всем "дефектам".
Из ограничений выше следует, что в каждом гиперслое единиц должно быть поровну, иначе числа для других осей в этот гиперслой не поместятся. То есть в тернарном случае в каждом слое должно быть по 3 единицы, в кватернарном - по 16 (там гиперслои - это кубы 4х4х4). Так повезло, что для каждой расстановки трех единиц в одном слое в тернарном случае дальше способов заполнить либо 2, либо 0 (если расстановка этих трех единиц в один ряд). В кватернарном случае, боюсь, будет все сложнее, и просто умножением на степень двойки не отделаться.
Итого количество "дефектов" для кватернарного случая равно 64! / (16!)^4, что довольно много, поэтому объединять их в классы эквивалентности - хорошая идея. Но что-то классов эквивалентности тоже пока получается много)
По некоторым пунктам:
3. В качестве представителя можно взять лексикографически максимальный по всем эквивалентным объектам. Представителей всех классов эквивалентности (а значит и сами классы) можно найти перебором с отсечениями. Просто генерируем элементы объектов в порядке учета их в лексикографическом порядке, применяем действия группы, если удалось перемешать элементы объекта так, что получился объект лексикографически больше - то окатываемся.
4. Можем. Для этого надо представить каждый элемент группы в виде последовательности базовых действий группы. Например, для куба 4х4х4: сначала вращение, потом перестановка слоев по оси x, потом по оси y, потом z. Теперь, пусть мы повращали и переставили слои по оси x. Тогда дальше у нас будут переставляться только блоки из 4 элементов. Но если множество этих блоков не совпадает с множеством блоков начального куба, то смысла их переставлять нет - там нет элементов стабилизатора.
Ну или можно глубже вникнуть в структуру группы. Например, для группы всех перестановок
мощность стабилизатора для объекта
(состоящего из
элементов), на который действует группа, равна произведению факториалов размеров подмножеств одинаковых элементов в
.
У меня еще есть непонятки по прочитанному. Я у себя в голове немного другую модель задачи построил, она на изложенную в статье не до конца накладывается. Например, мне не до конца понятно почему для последних двух линий (двух "гиперслоев" в кватернарном случае) надо домножать на какую-то фиксированную степень двойки. У меня двойки для тернарного случая вылезают из функции Ф.
Если что, я свою модельку закодил, и она тоже дает 10752 для тернарного случая. Но наверно поля комментария будут "слишком узки", чтобы расписывать ее во всех подробностях.
Ну норм группа, похожие штуки уже давно придуманы и даже используются на практике
https://ru.wikipedia.org/wiki/Нумерация_Гёделя
https://ru.wikipedia.org/wiki/Гладкое_число
https://ru.wikipedia.org/wiki/Алгоритм_Диксона
Из всего, что здесь написано, интерес представляют идеи использования дробных и отрицательных чисел в некоторых местах. Но, думаю, математики уже давно додумались до применения такого в своих задачах.
Но ведь можно было дать рандомное лечение только одному ребенку, в итоге получить одну смерть с вероятностью 50%, и 0 смертей тоже с вероятностью 50%.
— Что случилось? — спросил я. — Один из тех несчастных случаев на производстве, — сказал он.
Я никогда не мог заставить его рассказать об этом подробнее.
Он просто сказал: «Один из тех».
Это примерно как переписать программу без использования сторонних библиотек.
Кароси
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.
Еще у Вас, кстати, на 10^7 переполнение тут: