Establecer particiones en Python
tengo una variedad de[1,2,3]
Quiero hacer todas las combinaciones posibles usando todos los elementos del array:
Resultado:
[[1], [2], [3]]
[[1,2], [3]]
[[1], [2,3]]
[[1,3], [2]]
[[1,2,3]]
Dado que esta agradable pregunta ha vuelto a la vida, aquí tienes una nueva respuesta.
El problema se resuelve de forma recursiva: si ya tiene una partición de n-1 elementos, ¿cómo la usa para particionar n elementos? Coloque el enésimo elemento en uno de los subconjuntos existentes o agréguelo como un nuevo subconjunto único. Eso es todo lo que se necesita; no itertools, sin conjuntos, sin salidas repetidas y un total de solo n llamadas a partition():
def partition(collection):
if len(collection) == 1:
yield [ collection ]
return
first = collection[0]
for smaller in partition(collection[1:]):
# insert `first` in each of the subpartition's subsets
for n, subset in enumerate(smaller):
yield smaller[:n] + [[ first ] + subset] + smaller[n+1:]
# put `first` in its own subset
yield [ [ first ] ] + smaller
something = list(range(1,5))
for n, p in enumerate(partition(something), 1):
print(n, sorted(p))
Producción:
1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]
A diferencia de mis comentarios sugeridos, ¡no pude encontrar rápidamente una solución relativamente rápida basada en itertools! Editar: esto ya no es del todo cierto, tengo una solución bastante corta (pero lenta e ilegible) que utiliza itertools en gran medida; consulte el final de la respuesta. Esto es lo que obtuve en su lugar:
La idea es que encontremos todas las combinaciones de números enteros que suman la longitud de la lista y luego obtengamos listas con porciones de esa longitud.
Por ejemplo, para una lista de longitud 3, las combinaciones o particiones son (3), (2, 1), (1, 2) y (1, 1, 1). Entonces devolvemos los primeros 3 elementos de la lista; los 2 primeros y luego el 1 siguiente; el primero 1 luego los siguientes 2 y el primer 1, luego el siguiente 1, luego el siguiente 1.
Obtuve el código para la partición de números enteros desde aquí . Sin embargo, las funciones de partición no devuelven todas las permutaciones de las particiones (es decir, para 3 solo devolvería (3), (2, 1) y (1, 1, 1). Por lo tanto, debemos llamar itertools.permutationsa cada una de las particiones. Luego necesitamos eliminar los duplicados, tal como está permutations([1, 2, 3]). [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Una forma sencilla de eliminar duplicados es convertir cada lista de tuplas en un archivo .permutations([1, 1, 1])[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]]set
Entonces todo lo que queda es obtener porciones de la lista para las longitudes de la tupla. Por ejemplo, f([1, 2, 3], [0, 0, 1, 2, 1, 0])va a [[0], [0, 1], [2, 1, 0]].
Mi definición de eso es esta:
def slice_by_lengths(lengths, the_list):
for length in lengths:
new = []
for i in range(length):
new.append(the_list.pop(0))
yield new
Ahora simplemente combinamos todo:
def subgrups(my_list):
partitions = partition(len(my_list))
permed = []
for each_partition in partitions:
permed.append(set(itertools.permutations(each_partition, len(each_partition))))
for each_tuple in itertools.chain(*permed):
yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))
>>> for i in subgrups(my_list):
print(i)
[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
Además, también debe hacerlo import itertoolsen from copy import deepcopyla parte superior del programa.
Editar: el resultado proporcionado no está claro. Supuse que querías la función que te di, pero tu salida también contiene [[1,3],[2]], donde los elementos en la salida están en un orden diferente, a diferencia del resto de la salida sugerida (me he tomado la libertad de suponer que en realidad [[1, 2], [3]]no quieres [[1, 2], 3]) .
Es decir, supongo que lo que querías dar como resultado era esto:
[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
Si en realidad fuera esto:
[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
[[1], [3], [2]]
[[1], [3, 2]]
[[1, 3], [2]]
[[1, 3, 2]]
[[2], [1], [3]]
[[2], [1, 3]]
[[2, 1], [3]]
[[2, 1, 3]]
[[2], [3], [1]]
[[2], [3, 1]]
[[2, 3], [1]]
[[2, 3, 1]]
[[3], [1], [2]]
[[3], [1, 2]]
[[3, 1], [2]]
[[3, 1, 2]]
[[3], [2], [1]]
[[3], [2, 1]]
[[3, 2], [1]]
[[3, 2, 1]]
Luego simplemente necesita llamar subgrupspara cada permutación de 3 longitudes de la lista original, por ejemplo, para cada permutación en itertools.permutations(my_list, len(my_list)).
Editar: Ahora para cumplir mi promesa de una itertoolssolución breve. Advertencia: puede ser ilegible y lento.
Primero reemplazamos slice_by_lengthscon esto:
def sbl(lengths, the_list):
for index, length in enumerate(lengths):
total_so_far = sum(lengths[:index])
yield the_list[total_so_far:total_so_far+length]
Then from this answer we get our integer partitioning function:
def partition(number):
return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}
This function actually gets all permutations of the integer partitions for us, so we don't need
for each_partition in partitions:
permed.append(set(itertools.permutations(each_partition, len(each_partition))))
anymore. However, it is much slower than what we had before, as it is recursive (and we are implementing it in Python).
Then we just put it together:
def subgrups(my_list):
for each_tuple in partition(len(my_list)):
yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))
Or less readable, but without the function definitions:
def subgrups(my_list):
for each_tuple in (lambda p, f=lambda n, g:
{(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}:
f(p, f))(len(my_list)):
yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))
which is a function definition and two lines, so fairly close to what I originally stated (although much less readable and much slower)!
(Functions called subgrups because the question originally asked to find "all subgrups")
