Double self-join looking for items that add more unique value?

Question

I have a Dictionary<Key, <Quality,Item>> which is tracking the relationship between qualities and items. Qualities are an object type, Items are an object type, elsewhere I have lists of valid Qualities and valid Items. Items have a fixed list of qualities, always more than one. Qualities can be held by any number of items, including 0, depending on the state of the program.

Currently, Item objects also track their own Qualities in a List as one of my failed strategies to solve this. I have no idea if this is helpful or not, it's sure not helping me right now and will probably be ripped out if proved useless.

I already have a LINQ self-join that collects pairs of unique Items that share at least one Quality successfully.

var r = from KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_1
        in QualitiesToItems
        join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_2
        in QualitiesToItems
        on virtQ2I_1.Value.Item1.name equals virtQ2I_2.Value.Item1.name
        where (virtQ2I_1.Value.Item2.name != virtQ2I_2.Value.Item2.name)
        select new List<Item>
        {
            virtQ2I_1.Value.Item2, 
            virtQ2I_2.Value.Item2
        };

Afterwards I use another Dictionary to clean up the little burp where <ItemA, ItemB> are considered the same as <ItemB, ItemA>.

What Is Needed: A list of each triplet of unique Items that share at least one Quality with at least one other Item in the triplet. Big hairy complication: the third item in the triple can't just share one of the existing shared Qualities; it must bring something new to the relationship. And I need the results starting from a list of a few hundred Items quickly - my existing solution doesn't meet this last requirement.

Example:

• ItemA is Furry, Blonde, Four-Legged, and Trained
• ItemB is Furry, Rowan, Six-Legged, and Trained
• ItemC is Feathered, Blue, Two-Legged, and Trained

• ItemD is Scaled, Rowan, Slithers, and Untrained

  • ItemA and ItemB will already have been picked up as a valid pair, sharing the qualities Furry and Trained. (B:D of course are another valid pair, as are A:C and B:C)

  • ItemA, ItemB, and ItemC do not make a valid triplet as A:B are already Trained, and ItemC has nothing else in common with either ItemA or ItemB; A:B:C has the same Qualities list as A:B and therefor C is rejected as "supernumerary" or "redundant".

  • ItemA, ItemB, and ItemD make a valid triplet as ItemD forms a pair around Rowan with ItemB. The result of A:B:D is Furry, Rowan, Trained... and I need that combination of A:B:D to go in my list of returned results.

I'm having problems going from the way I'm getting my pairs to the way I need to get my triplets in a way that works on a few hundred items in reasonable time.

I thought I was very clever when I wrote a method to look for shared Qualities between two Items and used it in my new LINQ query, but the result is... quite slow when used on more than a score or so of items, and my computer is overpowered compared to some of the machines this will be running on.

var r = from KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_1 
        in QualitiesToItems 
        join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_2 
        in QualitiesToItems
        on virtQ2I_1.Value.Item1.name equals virtQ2I_2.Value.Item1.name
        join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_3
        in QualitiesToItems
        on virtQ2I_2.Value.Item1.name equals virtQ2I_3.Value.Item1.name
        where (virtQ2I_1.Value.Item2.name != virtQ2I_2.Value.Item2.name &&
        virtQ2I_1.Value.Item2.name != virtQ2I_3.Value.Item2.name &&
        virtQ2I_2.Value.Item2.name != virtQ2I_3.Value.Item2.name &&
        Item.SharedQualities(this, new Item[2] { virtQ2I_1.Value.Item2, virtQ2I_2.Value.Item2 }).Count !=
        Item.SharedQualities(this, new Item[3] { virtQ2I_1.Value.Item2, virtQ2I_2.Value.Item2, virtQ2I_3.Value.Item2 }).Count)
        select new List<Item>
        {
            virtQ2I_1.Value.Item2, 
            virtQ2I_2.Value.Item2, 
            virtQ2I_3.Value.Item2
        };

So: this worked, but I don't like it. Is there a way to replace my function calls (and new item arrays) mid query with something pure LINQ? There must be.

Answer 1

A little more head-bashing against the problem has provided a solution that does the worst of the heavy lifting in LINQ, and has much better performance than what I tried in the original post.

//collect two-pair items
var result = from KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_1
                    in QualitiesToItems
         join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_2
                 in QualitiesToItems
         on virtQ2I_1.Value.Item1.name equals virtQ2I_2.Value.Item1.name
         where (virtQ2I_1.Value.Item2.name != virtQ2I_2.Value.Item2.name)
         select new List<Item> {
                    virtQ2I_1.Value.Item2, 
                    virtQ2I_2.Value.Item2
                    };
List<List<Item>> ItemsForSets = result.ToList();

// self-join raw two-pair item list to generate three-set items
result =    from List<Item> leftSide in ItemsForSets 
        join List<Item> rightSide in ItemsForSets
        on leftSide[1] equals rightSide[0]
        where (leftSide[0] != rightSide[1])
        select new List<Item> {
                    leftSide[0], 
                    leftSide[1],
                    rightSide[1]
                    };

ItemsForSets.AddRange(result.ToList());

// clean up results - preventing A:B and B:A from being considered unique,
//    and ensuring all third ingredients actually contribute to a relationship.
foreach (List<Item> items in ItemsForSets)
{
    List<Quality> sharedQualities = Item.SharedQualities(this, items.ToArray());
    sharedQualities.Sort();
    List<String> sortedItems = items.ConvertAll(item => item.name); // I need the string names elsewhere 
    // TODO: I should rewrite to work directly with Items and convert after confirming I actually need the item.
    sortedItems.Sort(); // first part of preventing A:B B:A problems
    if (!Sets.ContainsKey(String.Join(", ", sortedItems))) // Dictionary provides second part.
    {
        if (items.Count == 3)
        {
            List<Quality> leftPairQualities = Item.SharedQualities(this, items.GetRange(0, 2).ToArray());
            leftPairQualities.Sort();
            if (leftPairQualities.SequenceEqual(sharedQualities))
            { // if the third item does not add a new quality
                continue; // short circuit out to the next item
            }
        }
        // otherwise add to the list.
        Sets.Add(String.Join(", ", sortedItems), new Potion(items, sharedQualities));
    }
}

I can do more clean-up, and I can probably replace the foreach with another LINQ query but that dynamites the big roadblock and significantly improves performance.