0

Estoy tratando de generar la tabla de Cayley para la composición de permutaciones (cada una con los números 1...n). Para ello lo que hago es generar todas las listas de posibles permutaciones y guardarlas en una lista. Luego creo una lista de listas (matriz) y los elementos que se guardan en esta matriz son los resultados de las composiciones entre la permutación correspondiente al índice de fila y la permutación correspondiente al índice de la columna (una permutación-lista). Luego intento generar la tabla mediante DataFrame de Pandas.

import itertools
import pandas as pd

def factorial ( curr ):
  if curr <= 1: return 1
  else: return curr * factorial( curr - 1 )

number_of_elements = 5
tot_num_permutations = factorial( number_of_elements )
init_permutation = list()
composition_matrix = [[ list() ] * tot_num_permutations ] * tot_num_permutations

for index in range( number_of_elements ):
  element = index + 1
  init_permutation.append( element )

permutations = list( itertools.permutations( init_permutation ))
aux_list = []

for n_row in range( tot_num_permutations ):
  for n_column in range( tot_num_permutations ):
    aux_list = []
    for pos in range( number_of_elements ):
      aux_list.append( permutations[ n_column ][ permutations[ n_row ][ pos ] - 1 ])
    composition_matrix[ n_row ][ n_column ] = aux_list

permutations_composition_table = pd.DataFrame( composition_matrix,
                                                index = permutations,
                                                columns = permutations )

permutations_composition_table

El problema es que las permutaciones resultantes salen en orden inverso y lo más importante, se repiten las permutaciones de la fila 0 en todas las demás.

1 respuesta 1

1

Lo primer de todo, para saber lo que está pasando, es hacer el ejemplo suficiente simple. En este caso, poner number_of_elements = 3 con 6 permutaciones es suficiente interesante y al mismo tiempo suficiente corto para tener una vista global.

El problema principal es que composition_matrix = [[ list() ] * tot_num_permutations ] * tot_num_permutations crea una matriz donde cada línea es el mismo elemento. Cambiando un elemento cambia todos los demás.

Se puede solucionar haciendo la iniciación como composition_matrix = [[list() for i in range(tot_num_permutations)] for j in range(tot_num_permutations)].

Aparte de eso, para hacer el código más "pythonico" seria emplear list comprehension al máximo. Eso evita muchos problemas con inicializar y cambiar, por que hace estos dos pasos en uno. Al principio, cuando uno está acostumbrado a otros lenguages de programación puede resultar un poco extraño y complejo para leer. Pero una vez acostumbrado, resulta más simple.

Pués, asi se puede escribir

init_permutation = [i + 1 for i in range(number_of_elements)]

Y

aux_list = [permutations[n_column][permutations[n_row][pos] - 1] for pos in range(number_of_elements)]

Pero también se puede combinar todo. Para entenderlo, se hace paso a paso, primero con aux_list, después con una línea entera, después con la matriz entera.

composition_matrix = [[[permutations[n_column][permutations[n_row][pos] - 1] for pos in range(number_of_elements)]
                       for n_column in range(tot_num_permutations)]
                      for n_row in range(tot_num_permutations)]

El código completo seria:

import itertools
import pandas as pd
import math

number_of_elements = 3
tot_num_permutations = math.factorial(number_of_elements)

init_permutation = [i + 1 for i in range(number_of_elements)]
permutations = list(itertools.permutations(init_permutation))
composition_matrix = [[[permutations[n_column][permutations[n_row][pos] - 1] for pos in range(number_of_elements)]
                       for n_column in range(tot_num_permutations)]
                      for n_row in range(tot_num_permutations)]
permutations_composition_table = pd.DataFrame(composition_matrix,
                                              index=permutations,
                                              columns=permutations)
print(permutations_composition_table)

Resultado:

           (1, 2, 3)  (1, 3, 2)  (2, 1, 3)  (2, 3, 1)  (3, 1, 2)  (3, 2, 1)
(1, 2, 3)  [1, 2, 3]  [1, 3, 2]  [2, 1, 3]  [2, 3, 1]  [3, 1, 2]  [3, 2, 1]
(1, 3, 2)  [1, 3, 2]  [1, 2, 3]  [2, 3, 1]  [2, 1, 3]  [3, 2, 1]  [3, 1, 2]
(2, 1, 3)  [2, 1, 3]  [3, 1, 2]  [1, 2, 3]  [3, 2, 1]  [1, 3, 2]  [2, 3, 1]
(2, 3, 1)  [2, 3, 1]  [3, 2, 1]  [1, 3, 2]  [3, 1, 2]  [1, 2, 3]  [2, 1, 3]
(3, 1, 2)  [3, 1, 2]  [2, 1, 3]  [3, 2, 1]  [1, 2, 3]  [2, 3, 1]  [1, 3, 2]
(3, 2, 1)  [3, 2, 1]  [2, 3, 1]  [3, 1, 2]  [1, 3, 2]  [2, 1, 3]  [1, 2, 3]
1
  • ¡Muchas gracias! Me has ayudado bastante e incluso dado unos consejos bastante valiosos.
    – jonat lop
    Commented el 14 mar. 2020 a las 20:58

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.