I have a set of objects with different attributes; e.g. a set of cars with colors, brand etc. I choose subsets by virtue of a specific set of attributes.

Now I want to identify pairs of such subsets that differ only by one element.

Eg. say I have 4 cars:

A: Red, Ford

B: Red, Ford

C: Blue, Ford

D: Green, Volvo

Then the set of “Ford” cars is [A,B,C] and the set of “Red” cars is [A,B], i.e. these two sets only differ by one element and would be identified. However the set of “Volvo” cars [D] differs by more than one element from all other possible subsets (looking only at subsets according to a specific set of attributes), and would not be identified as part of a pair.

Is there a generalized algorithm for this specific set problem/logic (identifying the existence of such sets), and/or solutions for identifying such sets that is smarter than generating and testing all possible permutations of possible sets against each other?

  • I don't understand what you mean by "subsets that differ only by one". How exactly do you compare one subset to another one? By comparing each elements of one subset to the elements of the other one and count their minmum(?) or maximum(?) different attributes? Need those subsets be disjoint? What is the result of comparing subset [D] with [A,D]? Currently, I have no idea what you are talking of. – Doc Brown Feb 15 '18 at 22:18
  • It's not clear if you're interested in algorithms for finding differences between two sets, or if you are looking for a more complex algorithm that analyses all the sets corresponding to some criteria. – Christophe Feb 15 '18 at 22:33
  • Clarified the question somewhat: by differing by one i mean two subsets (chosen by virtue of a specific set of attributes) include the same elements except one. In the exempel given, ther would be several subsets possible to generate: ”Red” cars, ”Blue” cars, ”Green” cars, ”Ford” cars, ”Volvo” cars, ”Red, Ford” cars, ”Blue, Ford” cars, ”Green, Volvo” cars, and ”All cars”. What im after is an algoritm that identifies these sets and which of them differ by one element only in the sets – Peder Feb 16 '18 at 6:15
  • 1
    @Peder: burying clarifying information in a comment is not helpful for other readers. Thus I took the freedom and tried to improve your question, please look at my edit and double check if I got your right (if not, feel free to improve or undo my edit). – Doc Brown Feb 16 '18 at 6:56
  • Is there a reason you cannot just look at the cardinality of the symmetric difference? – Tersosauros Feb 20 '18 at 5:34

The following code seems to do as you ask. It needs to extract and check the sets of each attributes objects against each other like so:

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))


[('Ford', 'Red')]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.