Find a combination of two elements that have not been viewed together (LINQ, SQL or C#)

Question

I have a page that displays two objects and then the user picks one of these. I record the preference and the combination in a MSSQL database and end up storing data like this:

UserId=1, BetterObjectId=1, WorseObjectId=2

Now I would like to avoid showing that combination of objects (1,2 / 2,1) ever again.

So how do I generate random combinations to show the user excluding previously viewed combinations?

This seems like it should be a really straightforward question but like most programmers I'm short on sleep and coffee so your help is much appreciated :-)

The very naive approach is something like this (and all calls to this function would have to be wrapped in a check to see if the user has already rated as many times as nCr where n is the item count and r is 2):

public List<Item> GetTwoRandomItems(int userId)
{
    Item i = null, i2 = null;
    List<Item> r = null;

    while (i == null || i2 == null)
    {
        r = GetTwoRandomItemsRaw();
        i = r[0];
        i2 = r[1];
        if (GetRating(i.Id, i2.Id, userId) != null) /* Checks if viewed */
        {
            i = null;
            i2 = null;
        }
    }
    return r;
}

private List<Item> GetTwoRandomItemsRaw()
{
    return Items.ToList().OrderBy(i => Guid.NewGuid()).Take(2).ToList();
}

Edits

Using some SQL I can generate a list of all items that aren't complete (i.e. there is a combination involving the item that the user hasn't seen) but I don't think is particularly useful.

I can also imagine generating every possible combination and eliminating already viewed ones before picking 2 random items but this is a another terrible solution.

A possibility (memory intensive for large n) is to generate all possible combinations and store the combinationId in the rating. Then I can just do a SELECT of all combinations WHERE combinationId IS NOT IN (SELECT combinationId FROM ratings WHERE userId=x) with some changes to reflect the symmetric relationship of combinations.

Answer 1

Table Item: ItemId
Table Rating: UserId, ItemId1, ItemId2, WinnerId

If you require that ItemId1 < ItemId2 in the Rating table, you only have to check the Rating table once.

var pair = db.Items.Join(db.Items,
  i1 => i1.ItemId,
  i2 => i2.ItemId,
  (i1, i2) => new {i1, i2}
)  //produce all pairs
.Where(x => x.i1.ItemId < x.i2.ItemId) //filter diagonal to unique pairs
.Where(x => 
  !db.Ratings
  .Where(r => r.UserId == userId
    && r.ItemId1 == x.i1.ItemId
    && r.ItemId2 == x.i2.ItemId)
  .Any() //not any ratings for this user and pair
)
.OrderBy(x => db.GetNewId()) //in-database random ordering
.First();  // just give me the first one

return new List<Item>() {pair.i1, pair.i2 };

Here's a blog about getting "random" translated into the database.

Answer 2

One solution is this:

SELECT TOP 1 i.id item1, i2.id item2 from item i, item i2 
WHERE i.id <> i2.id 
AND (SELECT COUNT(*) FROM Rating WHERE userId=@userId AND FK_ItemBetter=i.id AND FK_ItemWorse=i2.id) = 0
AND (SELECT COUNT(*) FROM Rating WHERE userId=@userId AND FK_ItemBetter=i2.id AND FK_ItemWorse=i.id) = 0
ORDER BY NEWID()

I wasn't aware of the cross join method of just listing multiple FROM tables before.

Answer 3

Assuming that the list of available items is in the database, I would handle this problem entirely in the database. You are hitting the database already, no matter what, so why not get it done there?

Answer 4

What about putting all the objects in a queue or a stack, and then pop 2 and 2 off until they are empty?