Tengo una lista como:
lst = [1,2,3,4,5,6,7,8,9,10]
y quiero obtener la combinación de todas las divisiones para un cubo n determinado sin cambiar el orden de la lista. Exp de salida para n=3:
[ [1],[2],[3,4,5,6,7,8,9,10], [1],[2,3],[4,5,6,7,8,9,10], [1],[2,3,4],[5,6,7,8,9,10], . . . [1,2,3,4,5,6,7,8],[9],[10], ]
Python es el lenguaje que uso, pero si me puede dirigir a un algoritmo, también sería bueno. Veo que este problema generalmente se aplica en cadenas. Pero no pude encontrarlo en la lista.
PD: esta es mi primera pregunta. Cualquier comentario es apreciado sobre cómo mejorar la pregunta.
Tratar:
from itertools import product def generate(n, l): for c in product(range(1, l), repeat=n - 1): s = sum(c) if s > l - 1: continue yield *c, l - s lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 3 for groups in generate(n, len(lst)): l, out = lst, [] for g in groups: out.append(l[:g]) l = l[g:] print(out)
Huellas dactilares:
[[1], [2], [3, 4, 5, 6, 7, 8, 9, 10]] [[1], [2, 3], [4, 5, 6, 7, 8, 9, 10]] [[1], [2, 3, 4], [5, 6, 7, 8, 9, 10]] [[1], [2, 3, 4, 5], [6, 7, 8, 9, 10]] [[1], [2, 3, 4, 5, 6], [7, 8, 9, 10]] [[1], [2, 3, 4, 5, 6, 7], [8, 9, 10]] [[1], [2, 3, 4, 5, 6, 7, 8], [9, 10]] [[1], [2, 3, 4, 5, 6, 7, 8, 9], [10]] [[1, 2], [3], [4, 5, 6, 7, 8, 9, 10]] [[1, 2], [3, 4], [5, 6, 7, 8, 9, 10]] [[1, 2], [3, 4, 5], [6, 7, 8, 9, 10]] [[1, 2], [3, 4, 5, 6], [7, 8, 9, 10]] [[1, 2], [3, 4, 5, 6, 7], [8, 9, 10]] [[1, 2], [3, 4, 5, 6, 7, 8], [9, 10]] [[1, 2], [3, 4, 5, 6, 7, 8, 9], [10]] [[1, 2, 3], [4], [5, 6, 7, 8, 9, 10]] [[1, 2, 3], [4, 5], [6, 7, 8, 9, 10]] [[1, 2, 3], [4, 5, 6], [7, 8, 9, 10]] [[1, 2, 3], [4, 5, 6, 7], [8, 9, 10]] [[1, 2, 3], [4, 5, 6, 7, 8], [9, 10]] [[1, 2, 3], [4, 5, 6, 7, 8, 9], [10]] [[1, 2, 3, 4], [5], [6, 7, 8, 9, 10]] [[1, 2, 3, 4], [5, 6], [7, 8, 9, 10]] [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]] [[1, 2, 3, 4], [5, 6, 7, 8, 9], [10]] [[1, 2, 3, 4, 5], [6], [7, 8, 9, 10]] [[1, 2, 3, 4, 5], [6, 7], [8, 9, 10]] [[1, 2, 3, 4, 5], [6, 7, 8], [9, 10]] [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10]] [[1, 2, 3, 4, 5, 6], [7], [8, 9, 10]] [[1, 2, 3, 4, 5, 6], [7, 8], [9, 10]] [[1, 2, 3, 4, 5, 6], [7, 8, 9], [10]] [[1, 2, 3, 4, 5, 6, 7], [8], [9, 10]] [[1, 2, 3, 4, 5, 6, 7], [8, 9], [10]] [[1, 2, 3, 4, 5, 6, 7, 8], [9], [10]]
Para una implementación manual, podría usar una función generadora recursiva:
def parts(lst, n): if 0 < n <= len(lst): if n == 1: yield [lst] else: for i in range(1, len(lst)-n+2): for part in parts(lst[i:], n-1): yield [lst[:i]] + part pprint(list(parts([1,2,3,4], 3))) # [[[1], [2], [3, 4]], # [[1], [2, 3], [4]], # [[1, 2], [3], [4]]] pprint(list(parts([1,2,3,4,5,6], 3))) # [[[1], [2], [3, 4, 5, 6]], # [[1], [2, 3], [4, 5, 6]], # [[1], [2, 3, 4], [5, 6]], # [[1], [2, 3, 4, 5], [6]], # [[1, 2], [3], [4, 5, 6]], # [[1, 2], [3, 4], [5, 6]], # [[1, 2], [3, 4, 5], [6]], # [[1, 2, 3], [4], [5, 6]], # [[1, 2, 3], [4, 5], [6]], # [[1, 2, 3, 4], [5], [6]]]
Un enfoque recursivo un poco más corto:
lst, n = [1,2,3,4,5,6,7,8,9,10], 3 def group(d, c = []): if not d and len(c) == n: yield c if d and c: yield from group(d[1:], c[:-1]+[c[-1]+[d[0]]]) if d and len(c) < n: yield from group(d[1:], c+[[d[0]]]) print(list(group(lst)))
Producción:
[[[1, 2, 3, 4, 5, 6, 7, 8], [9], [10]], [[1, 2, 3, 4, 5, 6, 7], [8, 9], [10]], [[1, 2, 3, 4, 5, 6, 7], [8], [9, 10]], [[1, 2, 3, 4, 5, 6], [7, 8, 9], [10]], [[1, 2, 3, 4, 5, 6], [7, 8], [9, 10]], [[1, 2, 3, 4, 5, 6], [7], [8, 9, 10]], [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10]], [[1, 2, 3, 4, 5], [6, 7, 8], [9, 10]], [[1, 2, 3, 4, 5], [6, 7], [8, 9, 10]], [[1, 2, 3, 4, 5], [6], [7, 8, 9, 10]], [[1, 2, 3, 4], [5, 6, 7, 8, 9], [10]], [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]], [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]], [[1, 2, 3, 4], [5, 6], [7, 8, 9, 10]], [[1, 2, 3, 4], [5], [6, 7, 8, 9, 10]], [[1, 2, 3], [4, 5, 6, 7, 8, 9], [10]], [[1, 2, 3], [4, 5, 6, 7, 8], [9, 10]], [[1, 2, 3], [4, 5, 6, 7], [8, 9, 10]], [[1, 2, 3], [4, 5, 6], [7, 8, 9, 10]], [[1, 2, 3], [4, 5], [6, 7, 8, 9, 10]], [[1, 2, 3], [4], [5, 6, 7, 8, 9, 10]], [[1, 2], [3, 4, 5, 6, 7, 8, 9], [10]], [[1, 2], [3, 4, 5, 6, 7, 8], [9, 10]], [[1, 2], [3, 4, 5, 6, 7], [8, 9, 10]], [[1, 2], [3, 4, 5, 6], [7, 8, 9, 10]], [[1, 2], [3, 4, 5], [6, 7, 8, 9, 10]], [[1, 2], [3, 4], [5, 6, 7, 8, 9, 10]], [[1, 2], [3], [4, 5, 6, 7, 8, 9, 10]], [[1], [2, 3, 4, 5, 6, 7, 8, 9], [10]], [[1], [2, 3, 4, 5, 6, 7, 8], [9, 10]], [[1], [2, 3, 4, 5, 6, 7], [8, 9, 10]], [[1], [2, 3, 4, 5, 6], [7, 8, 9, 10]], [[1], [2, 3, 4, 5], [6, 7, 8, 9, 10]], [[1], [2, 3, 4], [5, 6, 7, 8, 9, 10]], [[1], [2, 3], [4, 5, 6, 7, 8, 9, 10]], [[1], [2], [3, 4, 5, 6, 7, 8, 9, 10]]]