Permutaciones recursivas de tamaño k sin elementos iguales uno al lado del otro.

Answer

1. 

   davy.ai

   July 23, 2023 at 4:32 am

   Para crear permutaciones con repeticiones de tamaño k sin elementos repetidos uno al lado del otro, podemos utilizar un enfoque recursivo. Aquí hay un posible algoritmo:

   1. Definir una función llamada permutations_no_repeating_adjacent que tome dos argumentos: una lista items que contiene los elementos disponibles para elegir, y un entero k que especifica el tamaño de las permutaciones.
   2. Si k es 1, devolver una lista de tuplas de un solo elemento, cada una de ellas conteniendo uno de los elementos disponibles.
   3. De lo contrario, para cada elemento x en items, llamar de forma recursiva a la función permutations_no_repeating_adjacent con los elementos restantes y k-1, y concatenar los resultados para obtener todas las posibles permutaciones que comienzan con x.
   4. Filtrar las permutaciones que contengan dos elementos iguales consecutivos.
   5. Devolver la lista final de permutaciones.

   Aquí hay una posible implementación del algoritmo en Python:

   def permutations_no_repeating_adjacent(items, k):
       if k == 1:
           return [(x,) for x in items]
       else:
           result = []
           for x in items:
               subperms = permutations_no_repeating_adjacent([y for y in items if y != x], k-1)
               for subperm in subperms:
                   if len(subperm) == 0 or subperm[0] != x:
                       result.append((x,) + subperm)
           return result
   

   Para usar la función, simplemente llámala con la lista deseada de elementos y el valor de k:

   items = [1, 2, 3, 4]
   k = 4
   perms = permutations_no_repeating_adjacent(items, k)
   print(perms)
   

   Esto imprimirá una lista de 24 tuplas (en este ejemplo), cada una de ellas conteniendo una permutación de longitud k sin elementos iguales consecutivos.

Comments are closed.