Tengo una lista anidada

x = [['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]

Quiero hacer todas las permutaciones posibles de elementos en sublistas sin ir más allá de la sublista correspondiente. El resultado esperado son variaciones de algo como esto:

[['c', 'b', 'a'], ['d'], ['f', 'e', ['g', ['i', 'h']]]]
[['d'], ['a', 'b', 'c'], ['f', 'e', [['h', 'i'], 'g']]]

Cada elemento debe mantenerse se mantiene en su corchete.

Escribí este generador:

def swap(x):
    if isinstance(x, list):
        res = np.random.choice(x, len(x), replace = False)
        return [list(map(ff, res))]

    else:
        return x

Da variantes aleatorias del resultado esperado, pero necesito recolectarlas todas. ¿Cómo podría hacerlo? Deberia hacer:

my_list = []
for i in range(10000): # not necessary 10000, any huge number
    my_list.append(ff(yy1))

¿Y luego aplicar una función única a my_list para seleccionar las únicas, o hay otra opción?

1
manabou11 9 oct. 2019 a las 18:07

3 respuestas

La mejor respuesta

El isinstance() + itertools.permutations() es una buena dirección, solo necesitas un producto de ellos, y un poco de seguimiento cuya permutación se aplica a qué parte del árbol (?) (Estaba pensando en generar todos los recorridos posibles de un árbol):

import itertools

def plan(part,res):
  if isinstance(part,list) and len(part)>1:
    res.append(itertools.permutations(range(len(part))))
    for elem in part:
      plan(elem,res)
  return res

def remix(part,p):
  if isinstance(part,list) and len(part)>1:
    coll=[0]*len(part)
    for i in range(len(part)-1,-1,-1):
      coll[i]=remix(part[i],p)
    mix=p.pop()
    return [coll[i] for i in mix]
  else:
    return part

def swap(t):
  plans=itertools.product(*plan(t,[]))
  for p in plans:
    yield remix(t,list(p))

for r in swap([['a', 'b', 'c'], ['d'], ['e', 'f', ['g', ['h', 'i']]]]):
  print(r)

plan() encuentra recursivamente todas las listas "reales" (que tienen más de un elemento) y crea itertools.permutations() para ellas.

swap() llama a plan(), y luego combina las permutaciones en una sola megapermutación compuesta usando itertools.product()

remix() crea un objeto real para un solo paso de megapermutación. Es un poco complicado porque no quería pelear con el seguimiento de la posición del árbol, en su lugar, remix() funciona al revés, va a la última lista y lo mezcla con el último componente del plan actual, eliminándolo de la lista.

Parece funcionar, aunque su ejemplo es un poco largo, con entradas más simples tiene una salida manejable:

for r in swap([['a', ['b', 'c']], ['d'], 'e']):
  print(r)

[['a', ['b', 'c']], ['d'], 'e']
[['a', ['c', 'b']], ['d'], 'e']
[[['b', 'c'], 'a'], ['d'], 'e']
[[['c', 'b'], 'a'], ['d'], 'e']
[['a', ['b', 'c']], 'e', ['d']]
[['a', ['c', 'b']], 'e', ['d']]
[[['b', 'c'], 'a'], 'e', ['d']]
[[['c', 'b'], 'a'], 'e', ['d']]
[['d'], ['a', ['b', 'c']], 'e']
[['d'], ['a', ['c', 'b']], 'e']
[['d'], [['b', 'c'], 'a'], 'e']
[['d'], [['c', 'b'], 'a'], 'e']
[['d'], 'e', ['a', ['b', 'c']]]
[['d'], 'e', ['a', ['c', 'b']]]
[['d'], 'e', [['b', 'c'], 'a']]
[['d'], 'e', [['c', 'b'], 'a']]
['e', ['a', ['b', 'c']], ['d']]
['e', ['a', ['c', 'b']], ['d']]
['e', [['b', 'c'], 'a'], ['d']]
['e', [['c', 'b'], 'a'], ['d']]
['e', ['d'], ['a', ['b', 'c']]]
['e', ['d'], ['a', ['c', 'b']]]
['e', ['d'], [['b', 'c'], 'a']]
['e', ['d'], [['c', 'b'], 'a']]

24 permutaciones, como se esperaba

2
tevemadar 9 oct. 2019 a las 21:11

¿Has considerado usar itertools?

Hay herramientas explícitas de combinación y permutación disponibles.

Del docs:

itertools.permutations (iterable [, r])

Devuelve permutaciones sucesivas de longitud r de elementos en el iterable.

Si r no se especifica o es None, entonces r tiene el valor predeterminado de la longitud del iterable y se generan todas las permutaciones de longitud completa posibles.

Las permutaciones se emiten en orden de clasificación lexicográfica. Entonces, si la entrada iterable está ordenada, las tuplas de permutación se producirán en orden ordenado.

Los elementos se tratan como únicos según su posición, no según su valor. Entonces, si los elementos de entrada son únicos, no habrá valores repetidos en cada permutación.

itertools.combinations (iterable, r)

Devuelve subsecuencias de longitud r de elementos de la entrada iterable.

Las combinaciones se emiten en orden de clasificación lexicográfica. Entonces, si la entrada iterable está ordenada, las tuplas combinadas se producirán en orden ordenado.

Los elementos se tratan como únicos según su posición, no según su valor. Entonces, si los elementos de entrada son únicos, no habrá valores repetidos en cada combinación.

0
zhqiat 9 oct. 2019 a las 15:18

No particularmente pitónico, pero lo abordaría encontrando permutaciones de los índices, como se ve aquí:


from itertools import permutations
mylist= [[1], [1,2], [1,2,3]]
combinations = list(permutations([i for i in range(len(mylist))]))

print(combinations)

for item in combinations:
  print([mylist[item[i]] for i in range(len(mylist))])

Output:
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[[1], [1, 2], [1, 2, 3]]
[[1], [1, 2, 3], [1, 2]]
[[1, 2], [1], [1, 2, 3]]
[[1, 2], [1, 2, 3], [1]]
[[1, 2, 3], [1], [1, 2]]
[[1, 2, 3], [1, 2], [1]]
1
Jkind9 9 oct. 2019 a las 15:17
58307161