Introdução:

Um cubo de Rubik de 3x3x3 possui permutações possíveis, o que equivale a aproximadamente 43 quintilhões . Você já deve ter ouvido falar sobre esse número antes, mas como ele é realmente calculado? $43,252,003,274,489,856,000$

Um cubo de Rubik 3x3x3 tem seis lados, cada um com nove adesivos. Observando as peças (externas) em vez de adesivos, porém, temos seis peças centrais; peças de oito cantos; e doze peças de borda. Como os centros não podem ser movidos, podemos ignorá-los nos cálculos. Quanto aos cantos e arestas:

Existem( ) maneiras de organizar os oito cantos. Cada canto tem três orientações possíveis, embora apenas sete (dos oito) possam ser orientados independentemente; a orientação do oitavo / canto final depende dos sete anteriores, dadas ( ) possibilidades. $8!$ $40,320$ $3^7$ $2,187$
Existem ( ) maneiras de organizar as doze arestas. A metade deé porque as arestas devem estar sempre em uma permutação uniforme exatamente quando os cantos estão. Onze arestas podem ser invertidas independentemente, com o giro da décima segunda / aresta final, dependendo das onze anteriores, com ( ) possibilidades. $\frac{12!}{2}$ $239,500,800$ $12!$ $2^{11}$ $2,048$

Juntando isso, temos a seguinte fórmula:

8! \times 3^{7} \times \frac{12!}{2} \times 2^{11} = 43, 252, 003, 274, 489, 856, 000

$8!×3^7×\frac{12!}{2}×2^{11} = 43,252,003,274,489,856,000$

^{Fonte: Wikipedia - Permutações do cubo de Rubik}

Embora isso possa parecer bastante complexo, ainda é bastante simples para um cubo 3x3x3. Para cubos pares, a fórmula é um pouco diferente; esta é a fórmula para um cubo 4x4x4, por exemplo:

\frac{8! \times 3^{7} \times 24!^{2}}{24^{7}} = 7, 401, 196, 841, 564, 901, 869, 874, 093, 974, 498, 574, 336, 000, 000, 000

$\frac{8!×3^7×24!^2}{24^7} = 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000$

Que é aproximadamente 7,40 quattuordecilhões em pequena escala .

E para cubos NxNxN maiores (ou seja, o atual recorde mundial de 33x33x33), a fórmula será estendida um pouco. Para não tornar essa introdução muito longa, coloquei esses links aqui, onde as permutações do cubo 4x4x4 e alguns cubos NxNxN de outros tamanhos são explicados com uma fórmula resultante:

Você já deve estar se perguntando: existe uma fórmula geral baseada em para qualquer cubo x x ? Certamente existe. Aqui estão três algoritmos completamente diferentes, todos dando exatamente os mesmos resultados com base em : $N$ $N$ $N$ $N$ $N$

1: Fórmula de Chris Hardwick:

\frac{(24 \times 2^{10} \times 12!)^{N (\mod 2)} \times (7! \times 3^{6}) \times (24!)^{⌊ \frac{1 1}{4} \times (N^{2} - 2 \times N) ⌋}}{(4!)^{6 \times ⌊ \frac{1 1}{4} \times (N - 2)^{2} ⌋}}

$\frac{(24×2^{10}×12!)^{N\pmod2}×(7!×3^6)×(24!)^{\lfloor{\frac{1}{4}×(N^2-2×N)}\rfloor}}{(4!)^{6×\lfloor{\frac{1}{4}×(N-2)^2}\rfloor}}$

Experimente no WolframAlpha.

2: Fórmula trigonométrica de Christopher Mowla:

8! \times 3^{7} \times {(\frac{24!}{(4!)^{6}})}^{\frac{1 1}{4} \times ((N - 1 1) \times (N - 3) + \cos^{2} (\frac{N \times π}{2}))} \times (24!)^{\frac{1}{2} \times (N - 2 - \sin^{2} (\frac{N \times π}{2}))} \times (12! \times 2^{10})^{\sin^{2} (\frac{N \times π}{2})} \times \frac{1}{24^{\cos^{2} (\frac{N \times π}{2})}}

$8!×3^7×\left(\frac{24!}{(4!)^6}\right)^{\frac{1}{4}×((N-1)×(N-3)+\cos^2(\frac{N×\pi}{2}))}×(24!)^{\frac{1}{2}×(N-2-\sin^2(\frac{N×\pi}{2}))}×(12!×2^{10})^{\sin^2(\frac{N×\pi}{2})}×\frac{1}{24^{\cos^2(\frac{N×\pi}{2})}}$

Experimente no WolframAlpha.

3: Primos de Christopher Mowla Fórmula:

2^{\frac{1 1}{2} \times (2 \times N \times (N + 7) - 17 - 11 \times (- 1 1)^{N})} \times 3^{N \times (N + 1 1) + 2} \times 5^{\frac{1 1}{2} \times (2 \times N \times (N - 2) + 1 1 + (- 1 1)^{N})} \times 7^{\frac{1 1}{8} \times (6 \times N \times (N - 2) + 3 + 5 \times (- 1 1)^{N})} \times 11^{\frac{1 1}{4} \times (2 \times N \times (N - 2) - 1 1 + (- 1 1)^{N})} \times 96577^{\frac{1 1}{8} \times (2 \times N \times (N - 2) - 3 + 3 \times (- 1 1)^{N})}

$2^{\frac{1}{2}×(2×N×(N+7)-17-11×(-1)^N)}×3^{N×(N+1)+2}×5^{\frac{1}{2}×(2×N×(N-2)+1+(-1)^N)}×7^{\frac{1}{8}×(6×N×(N-2)+3+5×(-1)^N)}×11^{\frac{1}{4}×(2×N×(N-2)-1+(-1)^N)}×96577^{\frac{1}{8}×(2×N×(N-2)-3+3×(-1)^N)}$

onde é . $96577$ $(13×17×19×23)$

Experimente no WolframAlpha.

^{Fonte: Cubers-reddit - Fórmulas matemáticas de contagem de número de posições, número de Deus, etc.}

Desafio:

Escolha e implemente uma dessas três fórmulas (ou sua própria derivada), que fornece um número inteiro de entrada no intervalo , produz o resultado correto. $N$ $[2,100]$

Regras do desafio:

Você é livre para usar outra fórmula além dessas três, mas lembre-se de que essas três estão corretas. Se você usar outra fórmula, adicione um link de onde a obteve (ou, se você a criar, adicione uma explicação detalhada). E vou verificar todos os números inteiros no intervalo, se a saída estiver correta. Talvez a inspiração possa ser encontrada nos oeis para esta sequência: A075152 .
Se o seu idioma gerar automaticamente uma saída científica (ou seja, vez do número após a fórmula 4x4x4), isso é permitido. Mas adicione código adicional à sua resposta para converter esse arredondamento científico em uma saída exata para que os resultados possam ser verificados, pois não são permitidos erros de arredondamento devido à precisão do ponto flutuante durante a execução da fórmula em seu código - o resultado real deve ser exato. $1.401...×10^{45}$
Seu programa / função deve estar correto para pelo menos as entradas no intervalo (embora, como já resulte em um número imenso, qualquer maior provavelmente funcionará tão bem se você conseguir produzir isso um corretamente). $[2,100]$ $N=100$ $N$
Você não tem permissão para repetir todas as permutações possíveis com um contador, pois isso nunca produziria nada em um período de tempo razoável. Somente a implementação de uma fórmula (uma das três fornecidas, um derivado de uma delas ou uma fórmula completamente nova) ou outro método que fornecerá os resultados corretos em um período de tempo razoável (sem codificação embutida, é claro) ) é permitido. Pensei em adicionar um tempo restrito para impor isso, mas pessoalmente sou contra o tempo restrito em combinação com o código-golfe , então não o farei. Ainda assim, verifique se o seu programa fornece as respostas e, se for muito lento para o TIO, por algum motivo, adicione algumas capturas de tela com a saída da máquina local como verificação.

Regras gerais:

Isso é código-golfe , então a resposta mais curta em bytes vence.
Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
As regras padrão se aplicam à sua resposta com as regras de E / S padrão , para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno. Sua chamada.
As brechas padrão são proibidas.
Se possível, adicione um link com um teste para o seu código (ou seja, TIO ).
Além disso, é altamente recomendável adicionar uma explicação para sua resposta.

Casos de teste:

Aqui estão os casos de teste para no intervalo (fique à vontade para usar os links WolframAlpha acima para casos de teste maiores): $N$ $[2,10]$

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

NOTA: Como esse é um desafio do código-golfe , basicamente se resume a: implementar uma dessas três fórmulas (ou um derivado / seu próprio método que ainda produz os resultados corretos) o mais curto possível.

code-golf math number combinatorics rubiks-cube Kevin Cruijssen
fonte

2

Fazer isso no x86-64 será um desafio divertido. Vou ter que rolar meu próprio bigint (provavelmente apenas um int de 256 bits ou 512 bits) e torná-lo um golf.

moonheart08

11

@ moonheart08 Observe que, com N = 100, o resultado leva cerca de 128 Kb (16 KB): https://www.wolframalpha.com/input/?i=for+n+%3D+100,+N%5BLog%5B2, + ((24 * 2% 5E10 * 12!)% 5EMod% 5Bn, + 2% 5D + 7! 3% 5E6 + 24!% 5EPavimento% 5B (n% 5E2 + - + 2 + n)% 2F4% 5D)% 2F4!% 5E (6 + Piso% 5B (n + - + 2)% 5E2% 2F4% 5D)% 5D, 3% 5D

Solomon Ucko

4

Observe que a fórmula "trig" de Mowla apenas usa

e

para ofuscar s.

\sin^{2}

$\sin^2$

\cos^{2}

$\cos^2$ floor

attinat 18/04

4

@attinat, acho que é uma perspectiva mais útil dizer que tanto o trig e o piso estão ofuscando o

N mod 2

$N \bmod 2$

Peter Taylor

2

@ChristopherMowla Não tome seus comentários pessoais. Estou surpreso que você tenha conseguido encontrar essas fórmulas e tenha feito previsões tão precisas em primeiro lugar, e suas fórmulas foram uma das inspirações para esse desafio. No entanto, isso é código-golfe, portanto, legibilidade, desempenho, avisos, práticas recomendadas, significado histórico e, às vezes, apenas senso comum são jogados fora, se você pode salvar um único byte em uma resposta. ;) attinat e PeterTaylor simplesmente sugeriram esse tipo de golfe com base em suas fórmulas, pois o N mod 2 é um pouco mais curto para usar em linguagens de programação que o trig.

Kevin Cruijssen 23/04

12

Wolfram Language (Mathematica) , 59 bytes

f@n_:=(s=24^6)(24!/s)^(m=n-2)f@m
f@2=7!3^6
f@3=4!12!2^10f@2

Quantidade de permutações em um cubo de NxNxN Rubik

Introdução:

Desafio:

Regras do desafio:

Regras gerais:

Casos de teste:

Respostas:

Wolfram Language (Mathematica) , 59 bytes

código de máquina x86, 119 bytes

05AB1E , 38 bytes

Julia 1.0 , 83 76 bytes

Python 2 , 72 bytes

Wolfram Language (Mathematica) , 67 bytes

JavaScript (Node.js) , 81 bytes

JavaScript (Node.js) , 102 98 96 bytes

JavaScript (Node.js) , 77 75 73 bytes

Raquete , 151 141 bytes

Python 2 , 122 bytes

Geléia , 39 38 bytes

CJam (47 bytes)

Gelatina , 43 bytes

Ícone , 125 110 bytes

C (gcc) -lgmp, 279 bytes

Perl 6 , 85 bytes

Haskell , 86 85 74 bytes

Python 2 , 92 bytes

Casco , 51 48 44 bytes

C ++, 187 185 180 176 195 (houve um erro) 193 175 bytes (com ajuda do teto cat)

TI-BASIC, 63 62 bytes , (não competitivo)