Generating random couples in C#

Question

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 different 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 performance.

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 them 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

Answer 1

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()

Answer 2

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.

Answer 3

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";
}