tutorial - Establecer particiones en Python

para que se usa elastic search

Question

Tengo una serie de [1,2,3]

Quiero hacer todas las combinaciones posibles usando todos los elementos de la matriz:

Resultado:

[[1], [2], [3]]
[[1,2], [3]]
[[1], [2,3]]
[[1,3], [2]]
[[1,2,3]]

Answer 1

A diferencia de lo que sugerían mis comentarios, ¡no pude encontrar rápidamente una solución relativamente rápida basada en itertools! Edición: esto ya no es del todo cierto, tengo una solución bastante corta (pero lenta e ilegible) que usa itertools en gran parte, vea 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 se suman a la longitud de la lista y luego obtengamos listas con segmentos 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 artículos de la lista; los 2 primeros y luego el 1 siguiente; el primer 1, luego el siguiente 2 y el primero 1, luego el siguiente 1, luego el siguiente 1.

Tengo código para partición de enteros desde here . Sin embargo, las funciones de partición no devuelven todas las permutaciones de las particiones (es decir, para 3 simplemente devolvería (3), (2, 1) y (1, 1, 1). Por lo tanto, debemos llamar itertools.permutations en cada una de Las particiones. Luego necesitamos eliminar los duplicados, así como las permutations([1, 2, 3]) son [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ; permutations([1, 1, 1]) es [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] . Una forma fácil de eliminar duplicados es convirtiendo cada lista de tuplas en un set .

Luego, 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 solo 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 import itertools y from copy import deepcopy en la parte superior del programa.

Edición: su salida dada no está clara. Supuse que querías la función que te he dado, pero tu salida también contiene [[1,3],[2]] , donde los elementos de la salida están en un orden diferente, a diferencia del resto de tu salida sugerida (I ha tomado la libertad de suponer que realmente desea [[1, 2], [3]] no [[1, 2], 3] ).

Es decir, supongo que lo que querías dar como salida era esto:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

Si en realidad fue 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 subgrups para cada permutación de 3 longitudes de la lista original, por ejemplo, para cada permutación en itertools.permutations(my_list, len(my_list)) .

Edit: Ahora para cumplir con mi promesa de una solución corta basada en itertools . Advertencia: puede ser tanto ilegible como lento.

Primero reemplazamos slice_by_lengths con 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]

Entonces de this respuesta obtenemos nuestra función de partición de enteros:

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

Esta función realmente obtiene todas las permutaciones de las particiones de enteros para nosotros, por lo que no necesitamos

for each_partition in partitions:
    permed.append(set(itertools.permutations(each_partition, len(each_partition))))

nunca más. Sin embargo, es mucho más lento de lo que teníamos antes, ya que es recursivo (y lo estamos implementando en Python).

Luego lo juntamos:

def subgrups(my_list):
    for each_tuple in partition(len(my_list)):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

O menos legible, pero sin las definiciones de funciones:

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))

que es una definición de función y dos líneas, muy cerca de lo que originalmente dije (aunque mucho menos legible y mucho más lento)!

(Funciones llamadas subgrups porque la pregunta originalmente pidió encontrar "todos los subgrupos")

Answer 2

Desde que esta bonita pregunta ha sido devuelta a la vida, he aquí una nueva respuesta.

El problema se resuelve de forma recursiva: si ya tiene una partición de elementos n-1 , ¿cómo la usa para particionar n elementos? Coloque el elemento n ''th en uno de los subconjuntos existentes o agréguelo como un nuevo subconjunto de singleton. Eso es todo lo que se necesita; sin itertools , sin conjuntos, sin salidas repetidas, y un total de n llamadas a la 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))

Salida:

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]]