Введение:
Кубик Рубика 3x3x3 имеет возможных перестановок, что составляет приблизительно 43 квинтиллиона . Возможно, вы слышали об этом числе раньше, но как оно на самом деле рассчитывается?
Кубик Рубика 3х3х3 имеет шесть граней, каждая из которых имеет девять стикеров. Глядя на (внешние) части вместо наклеек, у нас есть шесть центральных частей; восемь угловых частей; и двенадцать краев. Поскольку центры не могут быть перемещены, мы можем игнорировать их в расчетах. Что касается углов и краев:
- Есть( ) способов расставить восемь углов. Каждый угол имеет три возможных ориентации, хотя только семь (из восьми) могут быть ориентированы независимо; ориентация восьмого / последнего угла зависит от предыдущих семи, учитывая ( 2 , 187 ) возможностей.
- Есть () способов расставить двенадцать ребер. Половина изэто потому, что ребра всегда должны быть вчетной перестановкеименно тогда, когда углы. Одиннадцать ребер могут быть перевернуты независимо друг от друга, при этом переворот двенадцатого / последнего ребра зависит от предыдущих одиннадцати, учитывая() возможностей.
Собирая это вместе, мы имеем следующую формулу:
Источник: Википедия - Перестановки кубиков Рубика
Хотя это уже может показаться довольно сложным, но для куба 3x3x3 все еще довольно просто. Для четных кубиков формула немного отличается; это формула для куба 4x4x4, например:
Что составляет примерно 7,40 кватурдесиллионов по короткой шкале .
А для больших кубов NxNxN (то есть текущего мирового рекорда 33x33x33) формула будет расширена совсем немного. Однако, чтобы не делать это введение слишком длинным, я поместил эти ссылки здесь вместо этого, где перестановки куба 4x4x4 и некоторых кубов NxNxN другого размера объясняются полученной формулой:
Вы можете задаться вопросом: есть ли общая формула, основанная на для любого куба x x ? Там, безусловно, есть. Вот три совершенно разных алгоритма, каждый из которых дает одинаковые результаты на основе :
1: Формула Криса Хардвика:
Попробуйте это на WolframAlpha.
2: Формула триггера Кристофера Моула:
Попробуйте это на WolframAlpha.
3: простые числа Кристофера Моула:
где является .
Попробуйте это на WolframAlpha.
Источник: Cubers-reddit - математические формулы подсчета количества позиций, числа Бога и т. Д.
Вызов:
Выберите и реализуйте одну из этих трех формул (или свою собственную производную), которая, учитывая входное целое число в диапазоне , выводит правильный результат.
Правила соревнований:
- Вы можете использовать другую формулу помимо этих трех, но имейте в виду, что эти три оказались правильными. Если вы используете другую формулу, пожалуйста, добавьте ссылку, откуда вы ее взяли (или, если вы придумали ее самостоятельно, добавьте подробное объяснение). И я проверю все целые числа в диапазоне, если вывод правильный. Возможно, в oeis можно найти вдохновение для этой последовательности: A075152 .
- Если ваш язык автоматически выводит научный вывод (т.е. вместо числа после формулы 4x4x4), это разрешается. Но, пожалуйста, добавьте дополнительный код в ваш ответ, чтобы преобразовать это научное округление в точный вывод, чтобы результаты могли быть проверены, поскольку ошибки округления из-за точности с плавающей запятой при выполнении формулы в вашем коде не допускаются - фактический результат должен быть точный.
- Ваша программа / функция должна быть правильной, по крайней мере, для входов в диапазоне (хотя, поскольку уже приводит к большому количеству заданий, любой больший , вероятно, будет работать так же хорошо, если вы сможете выведите это правильно).
- Вы не можете циклически перебирать все возможные перестановки со счетчиком, так как это никогда не выдаст ничего за разумное время. Только реализация формулы (либо одна из трех представленных, производная от одной из них, либо совершенно новая формула), либо другой метод, который даст правильные результаты за разумное время (без жесткого кодирования, конечно ) разрешено. Я думал о добавлении ограниченного времени для обеспечения этого, но я лично против ограниченного времени в сочетании с code-golf , поэтому я не буду. Тем не менее, пожалуйста, убедитесь, что ваша программа дает ответы, и, если по какой-то причине она слишком медленная для TIO, добавьте несколько скриншотов с выводом с вашего локального компьютера в качестве проверки.
Основные правила:
- Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте придумать как можно более короткий ответ для «любого» языка программирования. - Стандартные правила применяются к вашему ответу с правилами ввода / вывода по умолчанию , поэтому вам разрешено использовать STDIN / STDOUT, функции / метод с правильными параметрами и типом возврата, полные программы. Ваш звонок.
- По умолчанию лазейки запрещены.
- Если возможно, добавьте ссылку с тестом для вашего кода (например, TIO ).
- Кроме того, добавление объяснения для вашего ответа настоятельно рекомендуется.
Тестовые случаи:
Вот тестовые случаи для в диапазоне (не стесняйтесь использовать ссылки WolframAlpha выше для больших тестовых случаев):
n=2
3674160
n=3
43252003274489856000
n=4
7401196841564901869874093974498574336000000000
n=5
282870942277741856536180333107150328293127731985672134721536000000000000000
n=6
157152858401024063281013959519483771508510790313968742344694684829502629887168573442107637760000000000000000000000000
n=7
19500551183731307835329126754019748794904992692043434567152132912323232706135469180065278712755853360682328551719137311299993600000000000000000000000000000000000
n=8
35173780923109452777509592367006557398539936328978098352427605879843998663990903628634874024098344287402504043608416113016679717941937308041012307368528117622006727311360000000000000000000000000000000000000000000000000
n=9
14170392390542612915246393916889970752732946384514830589276833655387444667609821068034079045039617216635075219765012566330942990302517903971787699783519265329288048603083134861573075573092224082416866010882486829056000000000000000000000000000000000000000000000000000000000000000
n=10
82983598512782362708769381780036344745129162094677382883567691311764021348095163778336143207042993152056079271030423741110902768732457008486832096777758106509177169197894747758859723340177608764906985646389382047319811227549112086753524742719830990076805422479380054016000000000000000000000000000000000000000000000000000000000000000000000000000000000
ПРИМЕЧАНИЕ. Так как это задача для игры в гольф , она сводится к следующему: реализовать одну из этих трех формул (или производный / ваш собственный метод, который все еще дает правильные результаты) как можно короче.
источник
floor
Ответы:
Wolfram Language (Mathematica) , 59 байт
Попробуйте онлайн!
использует алгоритм Герберта Косиемба, найденный на странице OEIS
вот рекурсивная формула:
a(1)=1; a(2)=7!*3^6; a(3)=8!*3^7*12!*2^10; a(n)=a(n-2)*24^6*(24!/24^6)^(n-2)
6 байтов сохранено @Peter Taylor
еще один байт, сохраненный @Expired Data
источник
f@1
, поэтому вы можете сэкономить 6 байт. Очевидно, вы также захотите настроить свою тестовую среду для использованияRange[2,10]
.машинный код x86, 119 байт
HexDump:
Функция получает число
n
вecx
и указатель на строку для заполненияedx
(т.е.fastcall
соглашение).Прежде чем я покажу исходный код, некоторые пояснения о том, как это работает. Он использует рекурсивную формулу, которую я написал следующим образом:
Поэтому все, что должен делать код, это умножение на маленькие числа. Числа находятся в диапазоне 6 ... 36, который достаточно мал, чтобы быть представленным в 32-битном растровом изображении. Я на самом деле не храню бит, который представляет умножение на 6 - это позволяет мне расположить код в
do-while
цикле, начиная с безусловного умножения на 6.Большие числа представлены в десятичной форме - каждый байт является значением в диапазоне 0 ... 9, начиная с MSB.
Умножение выполняется от LSB до MSB; Предполагается, что число цифр будет расти на 2 для каждого умножения. После умножения на небольшой коэффициент, такой как 6, количество цифр может увеличиться только на 1. Поэтому, если MSB = 0, он сдвигает весь промежуточный результат влево. На самом деле может случиться так, что количество цифр совсем не увеличится, и тогда MSB все равно будет равен 0, но эта проблема исправится сама по себе, когда код переходит к большим факторам.
Поскольку код умножения большой, я не хочу ставить его дважды. Я также не хочу перемещать его в функцию, потому что машинный код для вызова функции велик. Поэтому я переставил внешние циклы таким образом, чтобы умножающий код был нужен только один раз.
Код C:
Разборка:
Время выполнения для n = 100 составляет около 4 секунд, и в результате получается число с 38416 цифрами:
23491019577617 (здесь много цифр) ... (здесь много нулей) 0000000000000000
источник
05AB1E , 38 байт
Начальная попытка
Использует формулу Криса Хардвика .
Попробую дальше поиграть в гольф и объяснить, когда у меня будет время.
Попробуйте онлайн!
источник
Юлия 1,0 ,
8376 байтПопробуйте онлайн!
Использует формулу Криса Хардвика. Принимает ввод как большое целое число.
Спасибо H.PWiz за -7 байт
источник
~=n->factorial(big(n))
->~n=prod(big,1:n)
и(24576*~12)^(n%2)
->^(24576*~12,n%2)
~=n->
вместо~n=
?Python 2 , 72 байта
Попробуйте онлайн!
Сохранено 4 байта путем копирования
n*(n-2)/4
с Нила .источник
Wolfram Language (Mathematica) , 67 байт
Используя формулу Криса Хардвика.
Попробуйте онлайн!
источник
JavaScript (Node.js) , 81 байт
Рекурсивная формула Герберта Косиембы. Принимает BigInt в качестве ввода.
Попробуйте онлайн!
JavaScript (Node.js) ,
102 9896 байтФормула Криса Хардвика. Принимает BigInt в качестве ввода.
Попробуйте онлайн!
источник
JavaScript (Node.js) ,
777573 байтаПопробуйте онлайн! Основано на формуле Кристофера Моула. Принимает BigInt в качестве ввода. Испытание жгута бесстыдно украдено у @Arnauld.
0xb88d4641131f0n
находится3246670537110000n
в десятичной системе счисления. Объяснение: я начал с последнего простого показателя и упростил его доn*(n-2n)/4n
(это целочисленное деление, поэтому мне не нужно корректировать нечетные числа). Затем я изучил другие простые числа, чтобы увидеть, были ли их показатели связаны с этим значением (которое я буду называтьo
), и обнаружил, что они были не в моде, если бы я позволил использовать паритетn
(который я буду обозначать какp
). Формулы для показателей следующие:Затем полномочия могут быть сгруппированы по показателю степени, например,
p
показатель степени11*7*5**2*3**3*2**14
.источник
Ракетка ,
151141 байт-7 байт благодаря fede s.!
Попробуйте онлайн!
Самый длинный ответ с использованием формулы Криса Хардвика :)
источник
expt
вызовов:(λ(n[e expt])...(e ...)...)
.Python 2 , 122 байта
Попробуйте онлайн!
Использует рекурсивный метод Герберта Косиемба.
-2 байта благодаря Herman L
источник
3**6
с 729 и2**10
с1024
TIOЖеле ,
3938 байтЯ чувствую, что пропустил несколько гольфов, но ...
Монадическая ссылка, реализующая формулу Криса Хардвика.
Попробуйте онлайн! Или посмотрите набор тестов (
n=[1..33]
).источник
CJam (47 байт)
Онлайн демо
Это реализует рекурсию Герберта Кочембы из OEIS:a ( n ) = ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪17 ! × 36a ( n - 1 ) × 3 × 12 ! × 213a ( n - 2 ) × ( 24 !246)п - 2× 246 если n∈{0,1} если n=2 если n=3 если n>3
используя запомнившийся оператор рекурсии CJam
j
. Я упорядочил термины в блоке MathJax в том же порядке, что и в коде, чтобы облегчить проверку соответствия для тех, кто читает CJam: любое дальнейшее изучение не будет проливать больше света.источник
Желе , 43 байта
Попробуйте онлайн!
источник
Icon ,
125110 байтПопробуйте онлайн!
источник
C (gcc) -lgmp, 279 байтов
Попробуйте онлайн!
источник
N--*--N/4
вместо(N*N-2*N)/4
и удалитьN-=2
и#define s mpz_init_set_str
Perl 6 , 85 байт
Попробуйте онлайн!
источник
Haskell ,
868574 байта-1 байт сохранен благодаря H.PWiz
-11 байт сохранен благодаря Максу Ехлакову
Попробуйте онлайн!
источник
24576
короче2^13*3
Python 2 , 92 байта
Попробуйте онлайн!
источник
Шелуха ,
514844 байта-4 байта благодаря H.PWiz
Попробуйте онлайн!
Это Формула Криса Хардвика. Кроме того, это моя первая программа шелухи, поэтому любые советы будут с благодарностью.
источник
÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24*1024Π12
÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24576Π12
C ++,
187 185 180 176 195 (была ошибка) 193175 байт (с помощью потолочного кота)При этом используется оболочка GMP C ++ (библиотека высокой точности GNU) и формула, используемая @ J42161217 ( https://codegolf.stackexchange.com/a/183381/55953 ).
Используйте
g++ -g rubix.cpp -lgmp -lgmpxx
для компиляции и ссылкиразряженный, с тестовым кодом
https://tio.run/##PZAxb4MwEIV3foWVDrETqBpARMImWZqha7t0iFQZ4xC3xrg2tJERf73UIVXfcE937zvpdEzrqGZsmu6EYrKvOKkbfbncn3dBb4WqgSsa7d6YpNZiBzR0gIYOlGhwgBUb/H0WksMyihBbFRQb3vVGAYZHB4xnFRr@Rqoo4n2SbdNN9pD7Jtk7uNCvafVEn7fvjx@LMItRbqCKYrTSME7D7OoeOpivl4Mp@eeMhFcAj//3AiJa2xlOm13QUKEgCoYAeJ1aA4XqgChiDARJUl/XazRnXrar8py1fUeIIGR57JaE@AUECLllXFUSB2Mw/bCTpLWdIjm/5ua/
источник
n=10
тестового примера, чтобы я мог убедиться, что он работает? Я думаю, что нет никакого способа заставить это работать на C ++ (clang) или C ++ (gcc) TIO из-за используемой библиотеки?TI-BASIC,
6362 байта , (неконкурентный)Выражение, которое принимает входные данные как целое число
Ans
. Реализация формулы Криса Хардвика. Неконкурентный, потому что аппаратное обеспечение, на котором он работает, будет хранить только до 16 десятичных знаков, поэтому ответ никогда не будет точным на 100%.Объяснение:
источник