views:

378

answers:

3

I have a table in my DB with a list of people. I need to create a list of random buddies every day.

The idea is that every day every person is paired with a differenct random person for that day.

Since the table may get very large I was wondering what would be the best way to do such a thing?

I have thought of 2 ideas but I am not so sure about them in regard to perf.

1) I use a random number generator to randomly pick two ids. The problem with that is that I have to constantly make sure the numbers weren't called yet and as I get close to the end of the list this can get real slow.

2) start every one off with the guy below then in the list and simply move down one every day until you get to the bottom at whcih point I move back to the top.

Any other ideas?

Thanks

+7  A: 

Perhaps you can make a query that sorts the table randomly, and then just pair people from the top down. The first entry gets paired with the second, third with the fourth and so on.

SQL Server example:

SELECT * FROM Table ORDER BY NEWID()
Fredrik Mörk
This is a very clever solution. Grab the entire list in a randomly sorted order,
Eoin Campbell
Great solution, but it would allow having the same pair two days in a row, if this is a requirement (in which case one must keep the history anyways)
van
Thanks this worked well. I did it using Linq OrderBy(x => random.GetNext());
Sruly
+1  A: 

It's not really that hard, using a random-generator isn't really slow but if you are very unlucky the time complexity will become O(n^2) and in best case O(1), how do you like that?

However, just have a table that connects two persons, see if their IDs occure which is fast, if it doesn't, just add their ID's, use T-SQL to loose extra connections.

Filip Ekberg
A: 

It seems to me this problem is already solved.

  1. You want to make lists of pairs.
  2. You want all lists of pairs (one for every day)

You don't need to use a random function for this. You just need to generate all lists of pairs.

The Permutation page on Wikipedia contains a few implementations of the algorithm that you need to use.

#!/usr/bin/perl -w
use strict;
use warnings;
use Data::Dumper;

sub permutation {
    my ($k, $s) = @_;

    for my $j (1..(@$s-1)) {
        my $n = ($k % $j) + 1;
        ($s->[$n], $s->[$j]) = ($s->[$j], $s->[$n]);
        $k = int($k / $j);
    }
    return $s;
}

for (1..3) {
    my $s = permutation($_, [1,2,3,4]);
    my ($a, $b, $c, $d) = @$s;
    print "$a\t$b\n";
    print "$c\t$d\n";
    print "------\n";
}
Peter Stuifzand
You'd probably still want to take a random permutation. Also generating each and every permutation migth be a little excessive for lists exceeding a handful of items :)
Joey
The number in the last for-loop could be a random number. That way you'll get one random permutation.
Peter Stuifzand
For example permutation(6, $people) will return the sixth permutation of the list. Choosing another (random) number will generate a different list of pairs.
Peter Stuifzand