es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Cómo encontrar todos los conjuntos más pequeños que no están contenidos en ningún otro conjunto.

Cómo encontrar todos los conjuntos más pequeños que no están contenidos en ningún otro conjunto.

13 Jul, 2023 Programación

Tengo un grupo de elementos que han sido ordenados en diferentes conjuntos. Estos conjuntos podrían tener intersecciones no nulas entre ellos. ¿Cómo puedo encontrar todos los conjuntos que no están contenidos en ninguno de los conjuntos existentes?

Por ejemplo:

  • elementos: a, b, c, d
  • conjuntos: {a, b, c}, {a, b}, {a}, {a, b, c, d}, {b, d, c}

En este caso, el resultado debería ser: {a}, {b, d, c}

  • {a, b, c, d} contiene {a, b, c} contiene {a, b} contiene {a}
  • {a, b, c, d} contiene {b, d, c}

Mi enfoque sería crear un grafo con:
– nodos que representen los conjuntos
– una arista entre el conjunto 1 y el conjunto 2 si el conjunto 1 está contenido en el conjunto 2

Una vez que construya el grafo, la solución serán las aristas sin predecesores (o aristas entrantes).

G = nx.DiGraph()

G.add_nodes_from([frozenset({‘a’, ‘b’, ‘c’}), frozenset({‘a’, ‘b’}), frozenset({‘a’}), frozenset({‘a’, ‘b’, ‘c’, ‘d’}), frozenset({‘b’, ‘d’, ‘c’})])

G.add_edges_from([(n, m) for n in G for m in G if n!=m if n<m])

print([n for n, in_degree in g.in_degree() if in_degree == 0]) print([n=”” for=”” n,=”” in_degree=”” in=”” g.in_degree()=”” if=”” in_degree=”=”></m])

print([n for n, in_degree in g.in_degree() if in_degree == 0])>

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Solución para encontrar conjuntos que no están contenidos en ningún conjunto existente

    Suponiendo que se nos da una lista de conjuntos y queremos encontrar todos los conjuntos que no están contenidos en ningún conjunto existente, podemos utilizar el siguiente enfoque:

    1. Crear un grafo donde cada conjunto es un nodo y hay una arista dirigida desde el conjunto A al conjunto B si A es un subconjunto de B.
    2. Encontrar todos los nodos en el grafo con grado de entrada 0, lo cual representa los conjuntos que no están contenidos en ningún conjunto existente. Podemos hacer esto utilizando un algoritmo de ordenamiento topológico.

    Aquí está una implementación de este enfoque en Python:

    import networkx as nx

items = {'a', 'b', 'c', 'd'}
sets = [{'a', 'b', 'c'}, {'a', 'b'}, {'a'}, {'a', 'b', 'c', 'd'}, {'b', 'd', 'c'}]

# Crear un grafo dirigido
G = nx.DiGraph()

# Agregar nodos al grafo
for s in sets:
    G.add_node(frozenset(s))

# Agregar aristas al grafo
for i, s1 in enumerate(sets):
    for j, s2 in enumerate(sets):
        if i != j and set(s1).issubset(set(s2)):
            G.add_edge(frozenset(s1), frozenset(s2))

# Encontrar todos los nodos con grado de entrada 0
result = [n for n, in_degree in G.in_degree() if in_degree == 0]
print(result)

    Salida:

    [frozenset({'a'}), frozenset({'b', 'd', 'c'})]

    Por lo tanto, los conjuntos que no están contenidos en ningún conjunto existente son {a} y {b, d, c}.

Comments are closed.