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

Question

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

Necesito enumerar todas las particiones de una matriz de N valores (N es constante) en k sub-arrays. Las sub-matrices son solo eso: un índice inicial y un índice final. Se conservará el orden general de la matriz original.

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

[ | a b c d ] (0, 4) 
[ a | b c d ] (1, 3) 
[ a b | c d ] (2, 2) 
[ a b c | d ] (3, 1) 
[ a b c d | ] (4, 0) 

Y con k = 3:

[ | | a b c d ] (0, 0, 4) 
[ | a | b c d ] (0, 1, 3) 
    : 
[ a | b | c d ] (1, 1, 2) 
[ a | b c | d ] (1, 2, 1) 
    : 
[ a b c d | | ] (4, 0, 0) 

Estoy bastante seguro de que esto no es un problema original (y no, no es tarea), pero me gustaría hacerlo por cada k < = N, y sería genial si los pases posteriores (a medida que k crece) aprovechen los resultados anteriores.

Si tienes un enlace, por favor comparte.

Answer 1

Para poder volver a utilizar los resultados anteriores (para valores menores de k), puede realizar recursiones.

Piense en tal 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 el primero).

Por lo tanto, el conjunto de partitionings son sólo un conjunto de todas las matrices de k enteros no decreciente entre 0 y N.

Si k está delimitado, puede hacerlo a través de bucles anidados k

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, puede hacerlo recursivamente.

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

• bucle "fin de la primera partición" EFP entre S y E. Para cada valor:

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

  • Para cada vector en esa lista, coloque previamente "EFP" en ese vector.

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

Tenga en cuenta que mi respuesta produce listas de puntos finales de cada rebanada. Si usted (como lo muestra su ejemplo) desea una lista de LONGITUDES de cada porción, necesita obtener las longitudes restando el último segmento final del segmento actual.

Answer 2

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

Para iterar sobre todos los subconjuntos de tamaño k-1, se puede extraer la pregunta:

How to iteratively generate k elements subsets from a set of size n in java?

La única arruga es que si se permite que las partes vacías, varios puntos de corte pueden coincidir, pero un subconjunto puede contener cada índice como máximo una vez. Vas a tener que ajustar el algoritmo ligeramente mediante la sustitución:

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

por

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