algorithm - relaciones - particion de un conjunto condiciones

generar todas las particiones de un conjunto

Question

Para un conjunto de la forma A = {1, 2, 3, ..., n} . Se llama partición del conjunto A , un conjunto de k<=n elementos que respetan los siguientes teoremas:

a) la unión de todas las particiones de A es A

b) la intersección de 2 particiones de A es el conjunto vacío (no pueden compartir los mismos elementos).

Por ejemplo. A = {1, 2,... n} Tenemos las particiones: {1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3}

Estos conceptos teóricos se presentan en mi libro de texto de algoritmos (por cierto, este subcapítulo es parte del capítulo "Retroceder"). Se supone que debo encontrar un algoritmo para generar todas las particiones de un conjunto dado. Estuve luchando con este problema todo el día y no pude encontrar una solución. ¿Puedes explicarme cómo funciona este algoritmo? Además, ¿puede darme un esbozo de pseudocódigo del algoritmo?

Answer 1

Puede probar la respuesta recursiva si su conjunto no es demasiado grande (o si no usa stack):

El principio es el siguiente, tienes una función que te devuelve:

rec_func(SET) = List of List of Set

Y trabaja de la siguiente manera:

rec_func(SET) =
  if SET = {empty}:
    // if no element, easy to give the answer
    return([[]])
  else:
    // 1. Remove one element from the set : ''a'' to this set
    a = SET.pop()
    // 2. Call rec_func :
    list_of_list_of_set = rec_func(SET/'a'')  
    response = []
    // 3. For every possibilities given by the function add the element ''a'' :
    For every list_of_set in list_of_list_of_set  :
       // Case 1, you add ''a'' to list_of_set
       response.push( [{''a''} + list_of_set] )
       // Case 2, for every set, you create a copy where you add ''a''
       for every set in list_of_set:
           response.push( [{set,''a''} + list_of_set/set] )

    // The function return the list of list of set created.        
    return(response)

Answer 2

Hay una observación importante (en un comentario) de que una partición de un conjunto de n elementos se puede representar como una secuencia entera de la forma [ p ₁ , ... p _n ] donde p _i es el número de partición del elemento i . Para que tal secuencia sea válida, debe obedecer las reglas de que p ₁ es 1, y para cada j donde 1 < j ≤ n , hay alguna i < j tal que p _j ≤ p _i & plus; 1. O, en otras palabras, en cualquier prefijo de la secuencia, no se salta ningún entero.

Ahora, hay un algoritmo estándar para enumerar secuencias restringidas en orden lexicográfico, que consiste en lo siguiente:

• Comience con la secuencia más pequeña.
• Para encontrar la siguiente secuencia en orden lexicográfico:
  • Explore hacia atrás la secuencia y encuentre el elemento "incrementable" que está a la derecha. (Un elemento incrementable es un elemento tal que hay un elemento más grande que podría ser sustituido por ese elemento, y la subsecuencia resultante hasta ese punto es un prefijo de al menos una secuencia válida).
  • Cambie ese elemento al siguiente elemento más grande que sea viable (es decir, que da como resultado un prefijo válido, como se indicó anteriormente), y luego complete los elementos restantes a su derecha (si corresponde) con los valores más pequeños posibles.
  • Si no hay un elemento incrementable, la enumeración ha finalizado.

Con varias disposiciones sobre la búsqueda de un elemento incrementable, este algoritmo es en el peor de los casos O ( n ) y a menudo es O ( 1 ) cuando el elemento a incrementar suele estar cerca del final de la secuencia. (Por ejemplo, usar este algoritmo para enumerar la permutación es O (1) para encontrar la siguiente permutación, siempre que pueda encontrar el "siguiente elemento" en O (1)).

Para aplicar este algoritmo al caso de partición, observamos lo siguiente:

1. La secuencia más pequeña posible es [1, ... 1]
2. Un elemento p _i es incrementable siempre que:
   • p _i < n
   • Hay algunos j < i tales que p _i & igual; p _j
3. El sufijo más pequeño de un prefijo viable es [1, ... 1]

Otra forma de establecer la condición en la observación 2 es que un elemento es incrementable a menos que su valor sea n o sea el primer elemento en la secuencia con su valor. Podemos hacer esa determinación en O (1) si también mantenemos la secuencia [ m ₁ , ... m _n ] donde m ₁ es 0, y m _i es el máximo de m _{i -1} y p _{i -1} . m es trivial de mantener, y nos permite reescribir la condición de escalabilidad simplemente como p _i ≤ m _i .

Es fácil ver que Next Partition se puede implementar en el tiempo O ( n ), pero sucede que también ocurre que se amortiza el tiempo O (1). En general, eso se debe a que en la mayoría de los casos, el último elemento de la secuencia es incrementable.

Answer 3

Estaba trabajando en un algoritmo eficiente que produce todas las particiones de un conjunto como se describió anteriormente, basado en el enfoque de palabras clave definido por @rici. El siguiente algoritmo, escrito en python, lo hace y todavía hay optimización posible. Estoy en eso. Como sabrá, este problema es NP completo. Debido a la optimización, tal vez haya alguna notación extraña como try / except. Sin embargo, las variables ny k están ahí para definir a través de n, cuántos elementos diferentes tiene el conjunto y la k es la cantidad de clases diferentes que los conjuntos pueden tener. INFO: ¡el algoritmo genera TODAS las particiones HASTA la cantidad de diferentes clases, no exclusivamente esas clases!

def partitions():
        global n
        global k
        codeword = [1 for digitIndex in range(0, n)]
        while True:
                print codeword
                startIndex = n - 1
                while startIndex >= 0:
                        maxValue = max(codeword[0 : startIndex])
                        if codeword[startIndex] > maxValue or maxValue > k or codeword[startIndex] >= k:
                                codeword[startIndex] = 1
                                startIndex -= 1
                        else:
                                codeword[startIndex] += 1
                                break

n = 12
k = 2
try:
        partitions()
except:
        pass