Have Geek Brain

Generating random pairs in C #

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

The idea is that every day each person is connected to another random person on that day.

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

I've thought of two ideas, but I'm not sure about them regarding performance.

1) I am using a random number generator to randomly select two IDs. The problem is that I have to constantly make sure that the numbers have not been called yet, and as I get closer to the end of the list, this can get very slow.

2) start each with the guy below them on the list and just work your way down every day until you get to the end, at which point I get back to the top.

Any other ideas?

thanks

+1


a source to share


3 answers


Perhaps you can make a query that sorts the table randomly and then just concatenate people from top to bottom. The first record connects to the second, the third to the fourth, etc.

SQL Server example:



SELECT * FROM Table ORDER BY NEWID()
+7


a source


Actually it's not that hard using a random generator, not very slow, but if you are very unlucky the time complexity becomes O (n ^ 2) and at best O (1) as you like



However, you have a table that connects two persons, see if their ids are fast, if not, just add their ids, use T-SQL to free up additional connections.

+1


a source


It seems to me that this problem has already been solved.

  • You want to create lists of pairs.
  • You need all pair lists (one for each day)

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

The Permutation page on Wikipedia contains several implementations of the algorithm 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";
}
0


a source






More articles:


All Articles