Cómo obtener la máxima cantidad de tuplas que aún no están contenidas en otro conjunto?

23 Jul, 2023 Programación 0

Dado una lista de letras, digamos L=[‘a’,’b’,’c’,’d’,’e’,’f’] y una lista de tuplas, por ejemplo T=[(‘a’,’b’),(‘a’,’c’),(‘b’,’c’)].

Ahora quiero crear la máxima cantidad de posibles tuplas a partir de la lista L que no estén contenidas en T. Esto debe hacerse sin duplicados, es decir, (a,b) sería lo mismo que (b,a). Además, cada letra solo puede estar emparejada una vez con otra letra.

Mi idea era:

crear una lista de todas las posibles tuplas primero:

all_tuples = [(x,y) for x in L for y in L if x!=y]

ahora eliminar duplicados

unique_tuples = list(set([tuple(sorted(elem)) for elem in all_tuples]))

Ahora, crear un nuevo conjunto que empareje cada letra solo una vez con otra letra

visited=set()
output = []

for letter1, letter2 in unique_tuples:
   if ((letter1, letter2) or (letter2, letter1)) in T:
      continue

   if not letter1 in visited and not letter2 in visited:
      visited.add(letter1)
      visited.add(letter2)
      output.append((letter1,letter2))

print(output)

Sin embargo, esto no siempre da la máxima cantidad de posibles tuplas, dependiendo de lo que sea T. Por ejemplo, digamos que extraemos las posibles unique_tuples=[(‘a’,’b’),(‘a’,’d’),(‘b’,’c’)].

Si agregamos (‘a’,’b’) primero a nuestra salida, ya no podemos agregar (‘b’,’c’), ya que ‘b’ ya ha sido emparejado. Sin embargo, si agregamos (‘a’,’d’) primero, también podríamos obtener (‘b’,’c’) después y obtener la máxima cantidad de dos tuplas.

¿Cómo se puede resolver esto?

davy.ai

July 23, 2023 at 1:47 pm

Una posible solución para asegurar obtener la cantidad máxima de tuplas es utilizar una función recursiva que verifique todas las combinaciones posibles de tuplas que no violen las condiciones (que no estén contenidas en T y que no haya letras duplicadas). Comenzando con una lista de salida vacía, la función puede agregar cada tupla posible y llamarse a sí misma recursivamente con las tuplas restantes hasta que se hayan verificado todas las combinaciones posibles. Luego, la función puede devolver la combinación con el mayor número de tuplas.

Aquí hay un ejemplo de implementación de esta función recursiva:

def encontrar_max_tuplas(L, T):
    # crear una lista de todas las tuplas posibles
    todas_las_tuplas = [(x,y) for x in L for y in L if x != y]
    # eliminar duplicados
    tuplas_unicas = list(set([tuple(sorted(elem)) for elem in todas_las_tuplas]))
    # inicializar variables
    max_count = 0
    max_salida = []
    # función recursiva para verificar todas las combinaciones posibles
    def verificar_combinaciones(salida, restantes):
        nonlocal max_count, max_salida
        # caso base: no hay más tuplas para agregar
        if not restantes:
            # verificar si esta combinación tiene la mayor cantidad de tuplas
            if len(salida) > max_count:
                max_count = len(salida)
                max_salida = salida
            return
        # recorrer las tuplas restantes
        for tupla in restantes:
            # verificar si la tupla no está contenida en T y no tiene duplicados
            if ((tupla not in T) and (tupla[::-1] not in T)
                    and (tupla[0] not in [x[0] for x in salida] + [x[1] for x in salida])
                    and (tupla[1] not in [x[0] for x in salida] + [x[1] for x in salida])):
                # agregar la tupla a la salida y llamar a la función recursivamente con las tuplas restantes
                verificar_combinaciones(salida + [tupla], [x for x in restantes if x != tupla])

    # iniciar la función recursiva con la salida vacía y todas las tuplas únicas
    verificar_combinaciones([], tuplas_unicas)
    # devolver la combinación de tuplas con el mayor número de tuplas
    return max_salida

Para usar esta función con las listas de ejemplo L y T de la pregunta, podemos llamarla:

L = ['a', 'b', 'c', 'd', 'e', 'f']
T = [('a', 'b'), ('a', 'c'), ('b', 'c')]
max_tuplas = encontrar_max_tuplas(L, T)
print(max_tuplas)

Esto mostrará en pantalla la combinación con el máximo número de tuplas posibles: [(‘a’, ‘d’), (‘b’, ‘c’)].

es.davy.ai

¿Tienes una pregunta?

Cómo obtener la máxima cantidad de tuplas que aún no están contenidas en otro conjunto?

Answer

davy.ai