c# - Grouping algorithm for combinations -

let's have list of items, each item defined simple structure

struct simpleitem {     string category1;     string category2;     ...     string categoryn; } 

each item have series of values belonging categories. number of categories n known @ time of processing list , each items have same amount of categories , 1 value per category, there no duplicate items. however, each list can have different category set.

i'm looking way group these items categories in way if groups deconstructed single items combining each permutations of categories, i'll end original combinaisons, no duplicates.

a group result be:

struct grouped {     string[] category1;     string[] category2;     ...     string[] categoryn; } 

example

for sake of example, we'll limit 3 categories, there can n.

categories

animal, eye color, fur

choices "animal" category: cat, dog, rat, horse

choices "eye color" category: blue, yellow, green, red, orange

choices "fur" category: long, short, curly

if list had permutations 3 categories, end result be

group 1 :
animal      [cat, dog, rat, horse]
eye color [blue, yellow, green, red, orange]
fur            [long, short, curly]

if have sublist, example:

1. cat, blue, long
2. cat, blue, short
3. dog, blue, long
4. dog, blue, short
5. dog, green long
6. rat, red, short
7. rat, blue, short

let's call list, input (a)

after grouping these items group end : (there other possibilities). grouping criteria have less output groups possible.

group 1:
animal      [cat,     dog]
eye color [blue           ]
fur           [long, short]

group 2:
animal      [dog]
eye color [green ]
fur           [long]

group 3:
animal      [rat           ]
eye color [red, blue]
fur           [short        ]

let's call these groups, output (b)

as can see, combining each items of resulting groups, we'll end original input list of 7 elements in (a).

question

so, i'm trying write algorithm generates these groups. trying linq, open other suggestions. suggestion on how (b) (a)?

1. take each input , treat it's own group.
   • so, example, cat, blue, long becomes group of [cat], [blue], [long], each category having 1 item.
2. go through each group in list, starting first. pair each other group in list. combine pairs of groups single group if meet appropriate criteria.
   • the criteria merging groups if set of values n-1 of categories same, , exactly 1 category set not match. if case, create new group n-1 similar categories being same, , remaining category intersection of sets.
3. if find match, stop comparing pairs , start on first item in first group. (using deferred execution here helps you, don't bother pairing groups find match.)
4. if go through entire set without finding match done, there no more combinations made.

---

so, walking through example. first pair first , second groups. first 2 category sets same, third different, can merged. have list is:

1. [cat], [blue], [long, short]
2. [dog], [blue], [long]
3. [dog], [blue], [short]
4. [dog], [green], [long]
5. [rat], [red], [short]
6. [rat], [blue], [short]

next compare (new) first , second groups. both first , third categories don't match, no merge. next compare first , third, again, same 2 categories won't match. first group won't match others. move onto second group. pair third. can merged, first 2 categories different:

1. [cat], [blue], [long, short]
2. [dog], [blue], [long, short]
3. [dog], [green], [long]
4. [rat], [red], [short]
5. [rat], [blue], [short]

now start over, pairing first , second groups. match. first category different, second same, , third same. now:

1. [cat, dog], [blue], [long, short]
2. [dog], [green], [long]
3. [rat], [red], [short]
4. [rat], [blue], [short]

we'd compare first each of other three, none match. compare second other two, none match. third , fourth match, second category different:

1. [cat, dog], [blue], [long, short]
2. [dog], [green], [long]
3. [rat], [red, blue], [short]

finally we'll go through of combinations, none of groups match merge conditions, , we're done.