Permutacao Circular

O que é permutação circular

Permutação circular acontece quando você organiza n elementos distintos em uma fileira que se fecha em um círculo. A diferença básica em relação à permutação linear é que rotar a disposição inteira não gera uma arrangement nova. Sentar João na posição 1, Maria na 2 e Pedro na 3 é a mesma configuração circular que sentar Maria na 1, Pedro na 2 e João na 3, porque tudo girou no mesmo ângulo. A fórmula padrão é (n-1)!. Você fixa uma posição de referência para quebrar a simetria rotacional e conta como as n-1 peças restantes se rearranjam ao redor dela. Nada muito complexo no papel.

Calcular permutacao circular na prática

O método direto funciona assim. Você pega o número total de pessoas ou objetos, subtrai um e fatora o resultado. Para 5 pessoas ao redor de uma mesa redonda, são 4! = 24 disposições. Para 8, são 7! = 5040. O cálculo em si leva menos de um segundo. O que muita gente não percebe de imediato é que esse cálculo assume implicitamente que o sentido horário e anti-horário contam como diferentes. Se você montar as peças fisicamente e conseguir virar o objeto para o outro lado, aí entra a permutação circular com reflexão, onde o resultado divide por mais 2. Para um colar com 6 contas distintas, por exemplo, passa de 5! = 120 para 60 arranjos. Sem essa correção, seu número sempre vai estar duplicado.

Eu já precisei aplicar isso num projeto de organização de turnos semanais para uma equipe de atendimento. A ideia era colocar as mesmas 7 pessoas em roda, rotacionando cada semana, e garantir que nenhum par ficasse sentado adjacentemente mais de uma vez num ciclo completo. A contagem pura de 6! me deu 720 configurações possíveis, mas o problema real era o filtro de restrição. Eu escrevi um script simples em Python que gerava todas as permutações circulares de 7 elementos, normalizava cada uma rodando o menor elemento para a primeira posição e depois aplicava uma verificação de pares adjacente a cada geração. Levei cerca de 3 minutos para o script rodar inteiro num notebook comum, filtrando de 720 para 30 arranjos que realmente atendiam à restrição. O ponto que quase me pegou foi que, sem normalizar por rotação antes de comparar, eu contava a mesma configuração circular repetidas vezes. Cada arranjo aparecia 7 vezes, uma para cada posição inicial. Dividir por n resolveu sem precisar de estruturas complicadas. Outro detalhe que parece óbvio mas causa erro constante é confundir permutação circular com arranjo circular onde certos elementos devem ficar juntos ou separados. Quando dois ou mais itens precisam permanecer adjacentes, você trata o grupo como um bloco único. Isso reduz o efetivo número de elementos em uma unidade e depois multiplica pelas permutações internas do próprio bloco. Dois elementos que precisam ficar juntos em uma mesa de 6 pessoas viram 5! × 2! = 240. Se forem três, vira 4! × 3! = 144. A lógica é simples até alguém pedir que dois elementos específicos fiquem em posições opostas. Aí você fixa um deles, o oposto tem apenas uma casa válida e o resto segue como uma permutação circular normal dos elementos restantes.

Existem casos em que a abordagem clássica simplesmente não entrega resposta útil. Se os elementos não são todos distintos, você precisa dividir pelo fatorial de cada grupo de repetidos dentro do (n-1)!, mas só depois de normalizar a simetria rotacional. Uma coroa com 6 contas onde 2 são vermelhas idênticas e 4 são azuis idênticas não tem resposta direta da fórmula simples; é necessário recorrer ao lema de Burnside ou enumerar manualmente com normalização. Eu tentei usar a fórmula padrão nesse caso e o resultado veio errado por fator de repetição. A correção com Burnside ficou clara em uma roda de 6 com duas cores iguais: as identidades por rotação e reflexão reduzem drasticamente o espaço, e o cálculo manual de órbitas entregou 3 configurações únicas, não 15 que a fórmula ingênua daria. Se você está lidando com um número grande de elementos e a restrição inclui simetria de reflexão junto com rotação, o campo começa a crescer rápido demais para enumeração pura. Para 10 ou mais elementos com restrições de adjacência múltiplas, um solver por força bruta em Python demora vários minutos e ocupa memória desnecessária. Nesses cenários, usar uma biblioteca como ortools ou até uma dinâmica sobre ciclos hamiltonianos com bitmask costuma ser mais rápido, porque evita gerar e descartar arruajos inválidos. O ganho real não está na matemática, que continua sendo (n-1)!, mas no filtro eficiente das restrições.

A parte chata que poucos aviso é sobre mesas ou anéis realmente indistinguíveis. A fórmula padrão assume que a orientação horária importa. Em problemas de anéis de DNA, colares físicos ou circuitos fechados onde você pode espelhar o objeto, a contagem correta precisa levar simetria Dihedral em conta. Se sua aplicação pede isso e você usa apenas (n-1)!, seu resultado estará sistematicamente alto em até o dobro. Verifique desde o início se o problema considera espelhamento como configuração diferente. Senão, aplique a divisão adicional por 2 para n maior que 2. Resumindo o que eu vejo no dia a dia: a fórmula é curta, a pegadinha está nas suposições sobre rotação, reflexão e repetições. Se souber qual simetria seu cenário realmente tem antes de calcular, evita maioria dos erros. E se as restrições ficarem complexas, aceite que a teoria sozinha não basta e passe para enumeration com normalização ou um solver dedicado, em vez de confiar em uma conta de papel que parece certa mas esconde uma simetria não considerada.