View Full Version : [Python] set intersection / itertools combinations...

11 November 2011, 11:42 PM
I try to find a good algorithm for a problem.
Here the problem :

I have a dictionary like this :

allGroups = {"property1":["object1", "object2", "object3", "object4"], "property2":["object1, "object2", "object4"], "property3":["object2", "object3", "object4"], "property4":["object1"], "property5":[]}

I want to generate some "groups" of objects with unique properties.
Like :
["object1"] have property1, property2, property4
["object2", "object4"] have property1, property2, property3
["object3"] have property1, property3
etc etc....
Each object can not be in another "group".

And obviously, i must to have the result in a dictionary to trace all object(s) with their properties, like :
{ ["property1", "property2", "property4"]:["object1"]}
{ ["property1", "property2", "property3"]:["object2", "object4"]}
for example, etc etc...

Anyone have a solution ? And if it is possible, without to parse all objects.
I tried to use set intersection or itertools.combinations, i failed.


11 November 2011, 07:55 AM
there's no easy answer to this. consider you have objects O1, O2, O3, O4 and properties P1, P2, P3, P4, grouped like that:

P1: O1, O2, O3
P2: O2, O3, 04
P3: O3, O4, O1
P4: O4, O1, O2

how would you group them? there's three equally viable cases:
P1, P2: O2, O3
P3, P4: O1, O4

P1, P3: O1, O3
P2, P4: O2, O4

P1, P4: O1, O2
P2, P3: O3, O4

And i'm not even touching a topic where in some cases you'd have to choose between prioritizing large groups or evenly-sized groups.

11 November 2011, 05:06 PM
If I understood you correctly, then:

1. Generate the inverse dictionary that would point from a property to a list of objects that has this property.

2. Hold a boolean array (actually a dictionary) on the side, which would have a 'already chosen' flag for each object.

3. To generate a group: Init the array in 2. Then iterate the dictionary from 1, and for each property add one object to the group if it isn't already there according to the flag array of 2. Update array2 accordingly.

In the same spirit you can choose randomly the size of the group (and try to create a group in size as close as possible to it), and you should iterate the properties in an order of some random permutation of them.

CGTalk Moderation
11 November 2011, 05:06 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.