algorithm - tiene - tipos de conjuntos

Estructura de datos rápida para encontrar subconjuntos estrictos(de una lista dada)

Question

Tengo un gran conjunto de conjuntos, por ejemplo {{2,4,5} , {4,5}, ...}. Dado uno de estos subconjuntos, me gustaría iterar a través de todos los demás subconjuntos que son subconjuntos estrictos de este subconjunto. Es decir, si estoy interesado en el conjunto A , por ejemplo, {2,4,5} , quiero encontrar todos los conjuntos B donde el complemento relativo B / A = {}, el conjunto vacío. Algunas posibilidades podrían ser {2,4} , {2,5} pero no {2,3}

Por supuesto, podría buscar linealmente y verificar cada vez, pero estoy buscando una estructura de datos eficiente tanto para el conjunto más grande como para el subconjunto (si es importante). El número de subconjuntos suele ser de 10 a miles, pero si hace una diferencia, me interesaría en los casos en que podría ser de cientos de millones. El tamaño de los subconjuntos es típicamente en 10s.

Estoy programando en C ++

Gracias

Answer 1

Eche un vistazo a esta biblioteca de python que implementa los diagramas de Hasse en python-lattice] 1

Answer 2

El enfoque sugerido por PengOne funcionaría, pero no es muy eficiente. Para ver por qué falla, considere el siguiente ejemplo patológico:

Supongamos que tiene un universo U, que tiene n elementos distintos, y deje que el conjunto de todos los conjuntos en los que está buscando conste de todos los subconjuntos de U con exactamente k elementos. Entonces es cierto que ningún par de conjuntos está estrictamente contenido uno en otro; y, en el peor de los casos, tendría que buscar en todos los n conjuntos k posibles. En otras palabras, usar su estructura de datos propuesta no es mejor que una búsqueda lineal ingenua en el peor de los casos.

Claramente, puedes hacerlo mucho mejor que esto, y la estructura de datos correcta a utilizar sería una prueba: http://en.wikipedia.org/wiki/Trie

Para adaptar un trie para trabajar con conjuntos en lugar de solo cadenas, es suficiente arreglar un orden en los elementos del conjunto universal, luego codificar cada uno de sus subconjuntos como una cadena binaria de longitud finita, donde el carácter i es 0 o 1 Dependiendo de si el conjunto contiene el elemento i. Aquí hay una implementación en python.

import math

class SetTree:
    def __init__(self, index, key, left, right):
        self.index = index
        self.key = key
        self.left = left
        self.right = right

cached_trees = { }
cached_index = 2

def get_index(T):
    if isinstance(T, SetTree):
        return T.index
    if T:
        return 1
    return 0        

def make_set_tree(key, left, right):
    global cached_trees, cached_index
    code = (key, get_index(left), get_index(right))
    if not code in cached_trees:
        cached_trees[code] = SetTree(cached_index, key, left, right)
        cached_index += 1
    return cached_trees[code]

def compute_freqs(X):
    freqs, total = {}, 0
    for S in X:
        for a in S:
            if a in freqs:
                freqs[a] += 1
            else:
                freqs[a] = 1
            total += 1
    U = [ (-f, a) for a,f in freqs.items() ]
    U.sort()
    return U

#Constructs the tree recursively
def build_tree_rec(X, U):
    if len(X) == 0:
        return False
    if len(U) == 0:
        return True

    key = U[0][1]

    left_elems = [ S for S in X if key in S]

    if len(left_elems) > 0:
        return make_set_tree(key,
            build_tree_rec(left_elems, U[1:]),
            build_tree_rec([ S for S in X if not key in S ], U[1:]))

    return build_tree_rec(X, U[1:])

#Build a search tree recursively
def build_tree(X):
    U = compute_freqs(X)
    return build_tree_rec(X, U)


#Query a set tree to find all subsets contained in a given set
def query_tree(T, S):
    if not isinstance(T, SetTree):
        return [ [] ] if T else []
    if T.key in S:
        return [ U + [ T.key ] for U in query_tree(T.left, S) ] + query_tree(T.right, S)
    return query_tree(T.right, S)

#Debugging function: Converts a tree to a tuple for printing
def tree_to_tuple(T):
    if isinstance(T, SetTree):
        return (T.key, tree_to_tuple(T.left), tree_to_tuple(T.right))
    return T

Ahora aquí hay un ejemplo de uso:

In [15]: search_tree = set_search.build_tree(set_family)

In [16]: set_search.tree_to_tuple(search_tree)
Out[16]: 
(2,
 (4, (5, True, True), (5, True, (3, True, False))),
 (4, (5, True, False), (1, True, False)))

In [17]: set_search.query_tree(search_tree, set([2,3,4,5]))
Out[17]: [[5, 4, 2], [4, 2], [5, 2], [3, 2], [5, 4]]

In [18]: set_search.query_tree(search_tree, set([1,2,3,4,5]))
Out[18]: [[5, 4, 2], [4, 2], [5, 2], [3, 2], [5, 4], [1]]

In [19]: set_search.query_tree(search_tree, set([2,4,5]))
Out[19]: [[5, 4, 2], [4, 2], [5, 2], [5, 4]]

In [20]: set_search.query_tree(search_tree, set([2,5]))
Out[20]: [[5, 2]]

In [21]: set_search.query_tree(search_tree, set([1]))
Out[21]: [[1]]

In [22]: set_search.query_tree(search_tree, set([15]))
Out[22]: []

Tenga en cuenta que la cantidad de trabajo realizado por query_tree es proporcional al tamaño del subárbol que representa el conjunto de todos los resultados devueltos por query_tree. Por lo tanto, nuestro objetivo es calcular el tamaño de uno de los subcontratos (en promedio) y luego como objetivo secundario para minimizar esta cantidad. Una forma de hacer esto es reordenar los elementos de lo universal en términos de frecuencia descendente, para que se repitan tan pocas veces como sea posible en los niveles más bajos del árbol. Esta optimización también se realiza en el código anterior. Una optimización secundaria es almacenar en caché los árboles que ya se han buscado para evitar tener que rehacer un trabajo innecesario.

EDIT: Justo después de que terminé de escribir esto, vi la respuesta de btilly, que llega a más o menos la misma conclusión sobre el problema (módulo, algunos problemas técnicos que he mencionado en los comentarios en su publicación).

EDIT 2: se dio cuenta de que esto es realmente un caso especial de un diagrama de decisión binario. Realmente no tengo suficiente energía para arreglar la escritura en este momento, por lo que la dejaré como está. Tal vez arreglarlo mañana. http://en.wikipedia.org/wiki/Binary_decision_diagram

Answer 3

Esto es interesante. Me gusta el enfoque del diagrama de Hasse que sugiere PengOne, pero creo que se puede construir el diagrama de Hasse realmente rápido usando un truco de números primos. Digamos que la unión de todos los conjuntos da como resultado los números naturales 1 a N. Mapea cada uno de estos números con los números primos correspondientes, como:

PrimeMap [1] = 2;
PrimeMap [2] = 3;
PrimeMap [3] = 5;

A continuación, calcule una ''puntuación'' para cada conjunto multiplicando cada uno de los números primos correspondientes al número en el conjunto. Por ejemplo, un conjunto {1,2,3} tendría una puntuación de 2 * 3 * 5 = 30. Ahora, para que un conjunto A sea un subconjunto adecuado de otro conjunto B, la puntuación (A) debe dividir la puntuación (B) (puntuaciones para {1,2}, {2,3} y {1,3} son 6, 15 y 10, cada uno de los cuales divide 30). Usa esta puntuación para construir tu diagrama Hasse.

Edit: Esta parece una de las buenas soluciones teóricas. Probablemente no sea el camino a seguir. Los conjuntos de bits sugeridos por yi_H son igual de buenos y no sufren grandes problemas de enteros.

Answer 4

Matemáticamente, debes construir el diagrama de Hasse para tus conjuntos, que será el conjunto parcialmente ordenado con vértices de tus conjuntos y flechas dadas por la contención. Esencialmente, desea crear un gráfico acíclico dirigido con una flecha A --> B si A contiene estrictamente B y no hay C modo que A contiene estrictamente C y C contiene B estrictamente.

Esto realmente va a ser un poset clasificado, lo que significa que puede realizar un seguimiento de los "niveles" del dígrafo en función de la cardinalidad de los conjuntos. Esto es algo así como crear una tabla hash para saltar al conjunto correcto.

Desde A , simplemente haga un BFS en el gráfico para encontrar todos los subconjuntos adecuados de A

Cómo implementar esto: (en pseudocódigo)

for (C in sets) {
    for (B in HasseDiagram at rank rank(C)+1) {
      if (C contains B)
        addArrow(C,B)
    }
    for (A in HasseDiagram at rank rank(C)+1) {
      if (C contains A)
        addArrow(A,C)
    }
    addToDiagram(C)
}

Para hacer esto y todas las subrutinas rápidas, puede codificar cada conjunto binario donde el dígito i es 1 si i está en C y 0 caso contrario. Esto hace que las pruebas de contención y la determinación del rango sean triviales.

El método anterior funciona si tienes todos los subconjuntos posibles . Como puede que te falten algunos, tendrás que revisar más cosas. Para el pseudocódigo, deberá cambiar el rank(C)-1 al entero más grande l < rank(C) manera que algún elemento del hasseDiagram tenga el rango l , y de manera similar para el rank(C)+1 . Luego, cuando estés agregando el conjunto C al diagrama:

1. Si A cubre a C , entonces solo necesita verificar los conjuntos B rango inferior que también están cubiertos por A

2. Si C cubre B , entonces solo necesitas marcar los conjuntos A mayor rango que también cubren con B

Por " X cubre Y " quiero decir que hay una flecha X -> Y , no solo un camino.

Además, cuando inserte C entre A y B utilizando uno de los controles anteriores, deberá quitar la flecha A --> B cuando agregue A --> C y C --> B

Answer 5

Yo sugeriría almacenar todos los conjuntos en un árbol. Cada nodo del árbol representaría todos los conjuntos que contenían una lista inicial de enteros especificada. Me gustaría que los nodos contengan la siguiente información:

1. La cantidad de elementos adicionales en el conjunto más pequeño en este punto o debajo del árbol. (0 significa que este nodo está en el árbol.)
2. Un conjunto de bits que representa la intersección de todos los subconjuntos debajo de éste en el árbol.
3. Un puntero a una matriz que asigna enteros más grandes a subárboles que lo contienen como el siguiente elemento. Como caso especial, si solo hay un subconjunto debajo de este en el árbol, este puntero podría ser nulo. (No es necesario rellenar las partes no pobladas del árbol).

Dado este árbol y un subconjunto, puede hacer una búsqueda con recursión y retroceso para todos los subconjuntos del conjunto. En su búsqueda, comienza con el primer elemento del subconjunto, busque todos los subconjuntos que contengan ese elemento, luego busque todos los subconjuntos que no contengan ese elemento.

La construcción de este árbol requiere tiempo y espacio como máximo O(n * m * k) donde n es el número de subconjuntos m es el número promedio de elementos por subconjunto, y k es el tamaño del universo de elementos que pueden estar en los conjuntos . Con conjuntos aleatorios de conjuntos que son mucho más pequeños que el posible universo de subconjuntos de sus k elementos, no construirá la mayor parte del árbol y tomará O(n * m) para su árbol.

En teoría, atravesar este árbol podría ser el tiempo O(n) . Pero en la práctica recortará las ramas del árbol bastante pronto y no atravesará la mayoría de los otros subconjuntos. Una parte posterior del cálculo de la envoltura sugiere que si tiene n conjuntos aleatorios de un universo de k elementos con n << 2 k entonces la búsqueda del árbol es O(n 0.5 k) . (En cada entero, la mitad del tiempo que está en su conjunto está buscando subconjuntos y dividió su búsqueda en 2, y la mitad del tiempo no está en su conjunto y eliminó la mitad de su espacio. Después de j enteros tienes 2 j/2 búsquedas que van de conjuntos de conjuntos de tamaño 2 -j n . Por lo tanto, cuando las búsquedas se reducen a otros subgrupos con los que comparar, existen O(n 0.5 ) búsquedas en curso. la comparación de mapas de bits es O(k) .)

Nota : Estoy convencido por esta parte posterior del cálculo del sobre que el rendimiento promedio es o(n 0.5+epsilon ) para cada epsilon > 0 , pero la convergencia es muy lenta. Más precisamente, sospecho que el promedio aritmético del rendimiento es n 0.5 + O(sqrt(log(n))) ) . Pero esa pieza sqrt(log(n)) tarda mucho tiempo en converger.

Tenga en cuenta que el uso de la cantidad de elementos adicionales en el conjunto más pequeño en este punto o debajo del árbol le permite a su búsqueda filtrar de forma trivial todos los conjuntos que son demasiado grandes para ser subconjuntos. Dependiendo de su conjunto de datos, esto puede o no conducir a aceleraciones útiles.