Identifica i set che differiscono di uno

Question

Identifica i set che differiscono di uno

#1 da (0 voti)

-3

Ho un set di oggetti con attributi diversi; per esempio. un set di auto con colori, marca, ecc. Scelgo i sottoinsiemi in virtù di un insieme specifico di attributi.

Ora voglio identificare coppie di tali sottoinsiemi che differiscono solo di un elemento.

Eg. Diciamo che ho 4 auto:

A: Rosso, Ford

B: rosso, Ford

C: blu, Ford

D: Green, Volvo

Quindi il set di auto "Ford" è [A, B, C] e l'insieme delle auto "rosse" è [A, B], cioè questi due set differiscono solo di un elemento e verrebbero identificati. Tuttavia, il set di vetture "Volvo" [D] differisce di più di un elemento da tutti gli altri sottoinsiemi possibili (guardando solo sottoinsiemi in base a un set specifico di attributi) e non verrebbe identificato come parte di una coppia.

Esiste un algoritmo generalizzato per questo specifico problema / logica (che identifica l'esistenza di tali insiemi) e / o soluzioni per identificare tali insiemi che è più intelligente della generazione e del test di tutte le possibili permutazioni di insiemi possibili l'uno contro l'altro?

algorithms math

posta Peder 15.02.2018 - 22:34

fonte

1 risposta

Leggi altre domande sui tag algorithms math

È possibile creare un'applicazione con html + css + javascript solo [chiuso] Dichiarazione di variabili multiple, assegnazione di più variabili, istruzione "in" sensibile al contesto

score 0 · Answer 1

Il seguente codice sembra fare come chiedete. Ha bisogno di estrarre e controllare gli insiemi degli oggetti degli attributi l'uno contro l'altro in questo modo:

objects = {
    'A': {'Red', 'Ford'},    
    'B': {'Red', 'Ford'},
    'C': {'Blue', 'Ford'},
    'D': {'Green', 'Volvo'},
    }

attributes = set()
for atts in objects.values():
    attributes |= atts
attribute2objects = {att: set(k for k, v in objects.items() if att in v) for att in attributes}
diffby1 = set()
for att1 in attribute2objects:
    for att2 in attribute2objects:
        if att1 != att2:
            ob1 = attribute2objects[att1]
            ob2 = attribute2objects[att2]
            if len(ob2) > len(ob2):
                ob1, ob2 = ob2, ob1
                att1, att2 = att2, att1
            if len(ob1 - ob2) == 1 and len(ob2 - ob1) == 0:
                diffby1.add((att1, att2))
print(sorted(diffby1))

Output:

[('Ford', 'Red')]