Permutações conjugadas

17

Uma permutação de tamanho n é uma reordenação dos primeiros n números inteiros positivos. (ou seja, cada número inteiro aparece uma vez e exatamente uma vez). As permutações podem ser tratadas como funções que alteram a ordem de uma lista de itens de tamanho n . Por exemplo

(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]

Assim, permutações podem ser compostas como funções.

(4 1 2 3)(2 1 3 4) = (4 2 1 3)

Isso traz muitas propriedades interessantes. Hoje estamos focando na conjugação . Permutações y e x (ambos de tamanho n ) são conjugados sse existem permutações g e g -1 (também de tamanho n ) tal que

x = gyg-1

e gg -1 é igual à permutação de identidade (os primeiros n números na ordem correta).

Sua tarefa é fazer duas permutações do mesmo tamanho por meio de métodos de entrada padrão e decidir se são conjugados. Você deve gerar um dos dois valores consistentes, um se eles forem conjugados e outro se não forem.

Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Existem muitos teoremas sobre permutações conjugadas à sua disposição, então boa sorte e golfe feliz.

Você pode receber a entrada como um contêiner ordenado de valores (1-n ou 0-n) representando a permutação como acima, ou como uma função que pega um contêiner ordenado e executa a permutação. Se você optar por assumir a função, deve aceitá-la como argumento, em vez de tê-la com um nome predefinido.

Casos de teste

(1) (1) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True
code-golf decision-problem combinatorics permutations abstract-algebra Assistente de Trigo
fonte
Podemos considerar a entrada como uma função? Também podemos usar o tamanho n?
Xnor
@xnor Claro em ambos os aspectos. Não tenho certeza de como o primeiro irá ajudá-lo.
Wheat Wizard
As regras de entrada da função padrão permitem que a função seja assumida como predefinida, o que economiza bytes ao escrevê-la como argumento, se você permitir.
Xnor
@xnor Estamos falando dessa regra? Isso é para funções de caixa preta que permutações não são. Isso faz sentido porque esse consenso é projetado para permitir que linguagens sem ponteiros / objetos funcionem, enquanto aqui podem porque permutações podem ser representadas de outra forma.
Assistente de trigo
Eu estava, não pensei na distinção deles serem de caixa preta. Então aqui, a entrada pode ser uma função, mas apenas como um argumento explícito?
Xnor

Respostas:

6

Python 2 , 87 bytes

f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&f(P,k-1)

Experimente online!

Recebe entrada Pcomo um par de ambas as permutações e kseu comprimento. Saídas 1para conjugados e 0não.

Isso usa o resultado:

Duas permutações x e y são conjugadas exatamente se suas k -ésimas potências x k e y k têm um número igual de pontos fixos para cada k de 0 a n .

Duas permutações de conjugados satisfazem isso porque seus k -ésimos poderes também são conjugados, e a conjugação preserva a contagem de pontos fixos.

É menos óbvio que quaisquer duas permutações não conjugadas sempre diferem. Em particular, a conjugação é determinada pela lista classificada de comprimentos de ciclo, e estes podem ser recuperados a partir da contagem de pontos fixos. Uma maneira de mostrar isso é com álgebra linear, embora possa ser um exagero.

Seja X a matriz de permutação de x . Então, o número de pontos fixos de x k é Tr (X k ) . Esses traços são os polinômios simétricos da soma de potência dos valores próprios de X k com multiplicidade. Esses polinômios para k de 0 a n permitem recuperar os polinômios simétricos elementares correspondentes desses valores próprios e, portanto, o polinômio característico e, portanto, os próprios valores próprios.

Como esses autovalores são raízes da unidade correspondentes aos ciclos de x , a partir deles podemos recuperar os tamanhos dos ciclos e suas multiplicidades. Assim, nossa "assinatura" identifica a permutação até a conjugação.

xnor
fonte
6

J , 25 bytes 23 bytes 16 bytes

solução tácita de milhas :

-:&([:/:~#&>)&C.

Solução explícita do OP:

c=:4 :'-://:~"1#&>C.&>x;y'

Isso verifica se as permutações xey têm o mesmo tipo de ciclo, usando a C.função interna para produzir representações de ciclo.

   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1
Mathias Dolidon
fonte
1
Bem-vindo ao PPCG e bom primeiro post. Reduzi seu método para 16 bytes -:&([:/:~#&>)&C.usando um formulário tácito. Aqui está um link do TIO para testá-lo.
miles
Obrigado. :) Ainda sou um iniciante em J e, embora pareça utilizá-lo facilmente com formas explícitas, compor formas tácitas eficientes ainda exige muito pensamento para mim. Vou adicionar sua solução.
Mathias Dolidon
PS: também não contamos os caracteres das atribuições de funções? c=:
Mathias Dolidon
1
@MathiasDolidon Não, por consenso padrão, não contamos os caracteres necessários para a atribuição, pois a função pode ser usada como está (com parênteses, mas não contamos).
Erik the Outgolfer
1
ESTÁ BEM ! Atualizei retroativamente as contagens da solução explícita no título para levar isso em conta.
Mathias Dolidon
4

MATL , 20 19 17 16 bytes

xY@!"&G@)@b)X=va

Entrada: dois vetores de coluna (usando ;como separador). Saída: 1se conjugado, 0se não.

Experimente online! Ou verifique todos os casos de teste .

Explicação

Não foram utilizados teoremas sobre permutações (por pura ignorância); apenas força bruta e esses dois fatos:

  • Para duas permutações p e q , a composição pq é equivalente a usar p para indexar os elementos de q .

  • A condição x = gyg −1 é equivalente a xg = gy .

Código comentado:

x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display
Luis Mendo
fonte
2

Gelatina , 11 bytes

Œ!©Ụ€ịị"®⁸e

Experimente online!

Como funciona

Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.
Dennis
fonte
Tanto quanto eu entendo, é realmente o yque indexa em cada um g⁻¹, e não o contrário. Veja o exemplo (4 1 2 3)(2 1 3 4) = (4 2 1 3). Com sua abordagem, resultaria, em (1 4 2 3)vez disso, desde o segundo indexar no primeiro. Levando isso em conta, tenho uma solução de 12 bytes que ainda não vou estragar. :-)
Erik the Outgolfer
@EriktheOutgolfer Fixed.
Dennis
@ Dennis Mas eu não cheguei a essa conclusão com base na explicação, cheguei exatamente à mesma abordagem, exceto que eu tinha algo parecido Œ!©Ụ€⁹ịЀ®ị"⁸e(basicamente toda a indexação com argumentos invertidos), exceto mais curto depois de fazer grandes modificações. Eu não acho que g⁻¹ygé o mesmo que gyg⁻¹. Além disso, acho que sua resposta também pode se beneficiar dessas modificações, mas, como eu disse antes, ainda não quero estragar a diversão.
Erik the Outgolfer
Sim, é exatamente o mesmo. Se x = g⁻¹yg, então gxg⁻¹ = y, é xe ysão conjugados.
Dennis
Hm, eu sinto que eu deveria revelar a minha solução de 12 byte então:eŒ!ị"Ụị@¥€¥¥
Erik o Outgolfer
1

Casca , 9 bytes

¤¦ṠmöLU¡!

Retorna 1para conjugado e 0para não conjugado. Experimente online!

Explicação

A classe de conjugação de uma permutao P do G = [1,2, .., n] é determinada pela multiconjunto contendo o mínimo período de cada número em G sob P . Quando P é obtido no formato de lista, posso substituir L por P e obter o mesmo multiset. O programa calcula o multiset correspondente para cada entrada e verifica se um é um sub multiset da outra. Como eles têm o mesmo número de elementos, isso equivale a ser o mesmo multiset.

¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?
Zgarb
fonte
1

Perl, 61 58 57 bytes

Inclui +2paraap

Dê permutações baseadas em 0 como 2 linhas em STDIN

perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

O algoritmo é uma variação menor na solução da xnor

Esta versão mais antiga do código atinge um bug de perl e despeja o núcleo de várias entradas no meu perl mais recente 5.26.1, mas funciona em um perl mais antigo 5.16.3.

@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

É possivelmente mais um exemplo do meu antigo inimigo perlgolf, o fato de o perl não refecontar adequadamente sua pilha.

Ton Hospel
fonte
1

JavaScript (ES6), 66 64 bytes

(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

Se li as outras respostas corretamente, o problema é equivalente a contar os períodos de todos os elementos e verificar se as duas listas têm o mesmo número de cada período. Editar: economizou 1 byte graças a @Arnauld calculando um a menos que o período. Salve outro byte graças a @Arnauld, abusando das estranhas regras de coerção do JavaScript para comparar as matrizes. Outro byte pode ser salvo currying, mas eu não gosto de curry, a menos que seja frango tikka masala.

Neil
fonte