views:

425

answers:

4

Hi,

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.

A: 

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?

cdonner
Yeah that's why I had SQL listed as one of the possible solution methods.
Graphain
A: 

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

Svish
Would you save the stack for each user? Not sure this would yield every combination either.
Graphain
oh, this is web stuff and across sessions? i was just thinking plain C#. Wouldn't yield all possible combinations, but thought one of the goals was not seeing an object twice. Which would be the case in my solution. If website and across sessions, sql is probalby the way to go =)
Svish
Ah sorry to neglect the across sessions part. Yeah yours is good for stopping objects twice - I just needed something that included every combination. Thanks though :-)
Graphain
+1  A: 

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.

Graphain
+1  A: 
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.

David B
Thanks for the input! I wondered about storing winner seperate - at the moment it was WinnerId/LoserId, not Item1, Item2, Winner.
Graphain
It's a tradeoff between space and order-ability.
David B