¿Enumerar todas las k-particiones de la matriz 1d con N elementos?

Esto parece una simple solicitud, pero Google no es mi amigo porque la “partición” anota un montón de visitas en la base de datos y en el espacio del sistema de archivos.

Necesito enumerar todas las particiones de una matriz de valores N (N es constante) en k subarreglas. Los subconjuntos son solo eso: un índice inicial y un índice final. El orden general de la matriz original se mantendrá.

Por ejemplo, con N = 4 y k = 2:

[ | abcd ] (0, 4) [ a | bcd ] (1, 3) [ ab | cd ] (2, 2) [ abc | d ] (3, 1) [ abcd | ] (4, 0) 

Y con k = 3:

 [ | | abcd ] (0, 0, 4) [ | a | bcd ] (0, 1, 3) : [ a | b | cd ] (1, 1, 2) [ a | bc | d ] (1, 2, 1) : [ abcd | | ] (4, 0, 0) 

Estoy bastante seguro de que esto no es un problema original (y no, no es tarea), pero me gustaría hacerlo para cada k <= N, y sería genial si se aprobara más tarde (a medida que k crece ) aprovechó resultados anteriores.

Si tienes un enlace, por favor comparte.

Para reutilizar los resultados anteriores (para valores menores de k ), puede hacer recursión.

Piense en dicha partición como una lista de índices finales (el índice inicial para cualquier partición es solo el índice final de la última partición o 0 para la primera).

Por lo tanto, su conjunto de particiones son solo un conjunto de todas las matrices de k enteros no decrecientes entre 0 y N.

Si k está limitado, puede hacerlo a través de k bucles nesteds

 for (i[0]=0; i[0] < N; i[0]++) { for (i[1]=i[0]; i[1] < N; i[1]++) { ... for (i[10]=i[9]; i[10] < N; i[10]++) { push i[0]==>i[10] onto the list of partitionings. } ... } } 

Si k no tiene límites, puedes hacerlo recursivamente.

Un conjunto de k particiones entre los índices S y E se obtiene mediante:

  • Repetir el final de la primera partición EFP entre S y E. Para cada valor:

    • Busque recursivamente una lista de particiones k-1 entre EFP y S

    • Para cada vector en esa lista, precargue “EFP” a ese vector.

    • El vector resultante de longitud k se agrega a la lista de resultados.

Tenga en cuenta que mi respuesta produce listas de puntos finales de cada sector. Si usted (como muestra su ejemplo) quiere una lista de LONGITUDES de cada sector, necesita obtener longitudes restando el último extremo del sector al final del sector actual.

Cada partición puede ser descrita por los índices k-1 que separan las partes. Dado que el orden se conserva, estos índices no deben disminuir. Es decir, hay una correspondencia directa entre los subconjuntos de tamaño k-1 y las particiones que busca.

Para iterar sobre todos los subconjuntos de tamaño K-1, puede consultar la pregunta:

¿Cómo generar iterativamente k subconjuntos de elementos de un conjunto de tamaño n en java?

La única arruga es que si se permiten partes vacías, varios puntos de corte pueden coincidir, pero un subconjunto puede contener cada índice como máximo una vez. Tendrás que ajustar el algoritmo ligeramente reemplazando:

  processLargerSubsets(set, subset, subsetSize + 1, j + 1); 

por

  processLargerSubsets(set, subset, subsetSize + 1, j);