Permutations conjuguées

17

Une permutation de taille n est une réorganisation des n premiers entiers positifs. (ce qui signifie que chaque entier apparaît une fois et exactement une fois). Les permutations peuvent être traitées comme des fonctions qui modifient l'ordre d'une liste d'éléments de taille n . Par exemple

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

Ainsi les permutations peuvent être composées comme des fonctions.

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

Cela apporte beaucoup de propriétés intéressantes. Aujourd'hui, nous nous concentrons sur la conjugaison . Les permutations y et x (toutes deux de taille n ) sont conjuguées ssi il y a des permutations g et g -1 (également de taille n ) telles que

x = gyg-1

et gg -1 est égal à la permutation d'identité (les n premiers nombres dans le bon ordre).

Votre tâche consiste à prendre deux permutations de la même taille via des méthodes d'entrée standard et de décider si elles sont conjuguées. Vous devez sortir l'une des deux valeurs cohérentes, une si elles sont conjuguées et l'autre si elles ne le sont pas.

Il s'agit de code-golf, donc les réponses seront notées en octets, moins d'octets seront meilleurs.

Il y a beaucoup de théorèmes sur les permutations conjuguées qui sont à votre disposition, alors bonne chance et bon golf.

Vous pouvez prendre l'entrée comme un conteneur ordonné de valeurs (soit 1-n ou 0-n) représentant la permutation comme ci-dessus, ou comme une fonction qui prend un conteneur ordonné et effectue la permutation. Si vous choisissez de prendre la fonction, vous devez la prendre comme argument plutôt que de l'avoir sous un nom prédéfini.

Cas de test

(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 Post Rock Garf Hunter
la source
Pouvons-nous prendre la saisie comme une fonction? Peut-on aussi prendre la taille n?
xnor
@xnor Bien sûr sur les deux points. Je ne sais pas comment le premier vous aidera.
Post Rock Garf Hunter
Les règles d'entrée de fonction par défaut permettent de supposer que la fonction est prédéfinie, ce qui économise des octets en l'écrivant comme argument, si vous l'autorisez.
xnor
@xnor Parlons-nous de cette règle? C'est pour les fonctions de boîte noire qui ne le sont pas. Cela a du sens car ce consensus est conçu pour permettre aux langages sans fonction pointeurs / objets de rivaliser alors qu'ici ils le peuvent parce que les permutations peuvent être représentées autrement.
Post Rock Garf Hunter
J'étais, je ne pensais pas à leur distinction de boîte noire. Donc ici, l'entrée peut être une fonction, mais seulement comme argument explicite?
xnor

Réponses:

6

Python 2 , 87 octets

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)

Essayez-le en ligne!

Prend l'entrée avec Pune paire des deux permutations et kleur longueur. Sorties 1pour conjugués et 0non.

Cela utilise le résultat:

Deux permutations x et y sont conjuguées exactement si leurs k- èmes puissances x k et y k ont un nombre égal de points fixes pour chaque k de 0 à n .

Deux permutations conjuguées satisfont à cela car leurs k -èmes pouvoirs sont également conjugués, et la conjugaison préserve le nombre de points fixes.

Il est moins évident que deux permutations non conjuguées diffèrent toujours. En particulier, la conjugaison est déterminée par la liste triée des longueurs de cycle, et celles-ci peuvent être récupérées à partir des comptes de points fixes. Une façon de le montrer est l'algèbre linéaire, même si cela peut être exagéré.

Soit X la matrice de permutation de x . Alors, le nombre de points fixes de x k est Tr (X k ) . Ces traces sont les polynômes symétriques somme des puissances des valeurs propres de X k avec multiplicité. Ces polynômes pour k de 0 à n permettent de récupérer les polynômes élémentaires symétriques correspondants de ces valeurs propres, et donc le polynôme caractéristique et donc les valeurs propres elles-mêmes.

Puisque ces valeurs propres sont des racines d'unité correspondant aux cycles de x , nous pouvons récupérer les tailles de cycle et leurs multiplicités. Ainsi, notre "signature" identifie la permutation jusqu'à la conjugaison.

xnor
la source
6

J , 25 octets 23 octets 16 octets

solution tacite de miles :

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

Solution explicite d'OP:

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

Cela vérifie si les permutations x et y ont le même type de cycle, en utilisant la C.fonction intégrée pour produire des représentations de cycle.

   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
la source
1
Bienvenue sur PPCG et joli premier post. J'ai raccourci votre méthode à 16 octets -:&([:/:~#&>)&C.en utilisant un formulaire tacite. Voici un lien TIO pour l'essayer.
miles
Je vous remercie. :) Je suis toujours un débutant en J, et bien que je semble pouvoir l'utiliser facilement avec des formulaires explicites, la composition de formulaires tacites efficaces nécessite encore beaucoup de réflexion pour moi. J'ajouterai votre solution.
Mathias Dolidon
PS: ne comptons-nous pas aussi les caractères des affectations de fonctions? c=:
Mathias Dolidon
1
@MathiasDolidon Non, par consensus par défaut, nous ne comptons pas les caractères requis pour l'affectation, car la fonction peut être utilisée telle quelle (avec des parenthèses, mais nous ne les comptons pas).
Erik the Outgolfer
1
D'ACCORD ! J'ai mis à jour rétroactivement les décomptes de la solution explicite dans le titre pour en tenir compte.
Mathias Dolidon
4

MATL , 20 19 17 16 octets

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

Entrée: deux vecteurs de colonne (en utilisant ;comme séparateur). Sortie: 1si conjugué, 0sinon.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Aucun théorème sur les permutations utilisé (par pure ignorance); juste la force brute et ces deux faits:

  • Pour deux permutations p et q , la composition pq équivaut à utiliser p pour indexer les éléments de q .

  • La condition x = gyg −1 est équivalente à xg = gy .

Code commenté:

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
la source
2

Gelée , 11 octets

Œ!©Ụ€ịị"®⁸e

Essayez-le en ligne!

Comment ça fonctionne

Œ!©Ụ€ịị"®⁸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
la source
Pour autant que je comprends, c'est en fait yqui indexe dans chacun g⁻¹, et non l'inverse. Voir l'exemple (4 1 2 3)(2 1 3 4) = (4 2 1 3),. Avec votre approche, il en résulterait (1 4 2 3)plutôt, puisque le second indexe dans le premier. En tenant compte de cela, j'ai une solution de 12 octets que je ne gâcherai pas encore. :-)
Erik the Outgolfer
@EriktheOutgolfer Fixed.
Dennis
@ Dennis Mais je ne suis pas arrivé à cette conclusion sur la base de l'explication, je suis arrivé exactement à la même approche, sauf que j'avais quelque chose comme Œ!©Ụ€⁹ịЀ®ị"⁸e(essentiellement toute l'indexation avec des arguments inversés), sauf plus courte après avoir fait des modifications majeures. Je ne pense pas que ce g⁻¹ygsoit la même chose que gyg⁻¹. De plus, je pense que votre réponse peut également bénéficier de ces modifications, mais, comme je l'ai déjà dit, je ne veux pas encore gâcher le plaisir.
Erik the Outgolfer
Oui, c'est exactement pareil. Si x = g⁻¹yg, alors gxg⁻¹ = y, alors xet ysont conjugués.
Dennis
Hm, je pense que je devrais révéler ma solution à 12 octets alors:eŒ!ị"Ụị@¥€¥¥
Erik the Outgolfer
1

Coque , 9 octets

¤¦ṠmöLU¡!

Renvoie 1pour conjugué et 0pour non-conjugué. Essayez-le en ligne!

Explication

La classe de conjugaison d'une permutation P de L = [1,2, .., n] est déterminé par le multiset contenant le moins de chaque période en nombre L sous P . Lorsque P est pris sous forme de liste, je peux remplacer L par P et obtenir le même multiset. Le programme calcule le multiset correspondant pour chaque entrée et vérifie si l'un est un sous-multiset de l'autre. Puisqu'ils ont le même nombre d'éléments, cela équivaut à être le même 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
la source
1

Perl, 61 58 57 octets

Comprend +2pourap

Donner des permutations basées sur 0 sous forme de 2 lignes sur 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

L'algorithme est une variation mineure de celui de la solution de xnor

Cette ancienne version du code frappe un bogue Perl et vide le noyau pour plusieurs entrées sur mon dernier Perl 5.26.1, mais cela fonctionne sur un Perl plus ancien 5.16.3.

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

C'est peut-être encore une autre instance de mon ancien ennemi de Perlgolf, le fait que Perl ne recompte pas correctement sa pile.

Ton Hospel
la source
1

JavaScript (ES6), 66 64 octets

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

Si j'ai bien lu les autres réponses, le problème revient à compter les périodes de tous les éléments et à vérifier que les deux listes ont le même nombre de chaque période. Edit: sauvé 1 octet grâce à @Arnauld en calculant un de moins que la période. Enregistrement d'un autre octet grâce à @Arnauld en abusant des règles de coercition étranges de JavaScript pour comparer les tableaux. Un autre octet pourrait être sauvé par le curry mais je n'aime pas le curry à moins que ce soit du poulet tikka masala.

Neil
la source