Генерация случайных пар в C#

Question

У меня в БД есть таблица со списком людей.Мне нужно каждый день создавать список случайных друзей.

Идея состоит в том, что каждый день каждый человек находится в паре с другим случайным человеком на этот день.

Поскольку таблица может стать очень большой, мне было интересно, как лучше всего это сделать?

Я подумал о двух идеях, но не уверен в их эффективности.

1) Я использую генератор случайных чисел, чтобы случайным образом выбрать два идентификатора.Проблема в том, что мне приходится постоянно следить за тем, чтобы номера еще не были названы, и когда я приближаюсь к концу списка, это может стать очень медленным.

2) начинать каждый с парня, находящегося под ним в списке, и просто каждый день перемещаться вниз по одному, пока не дойдете до конца, и в этот момент я возвращаюсь наверх.

Есть еще идеи?

Спасибо

Answer 1

Возможно, вы можете сделать запрос, который сортирует таблицу случайным образом, а затем просто объединяет людей сверху вниз.Первая запись соединяется со второй, третья с четвертой и так далее.

Пример SQL-сервера:

SELECT * FROM Table ORDER BY NEWID()

Answer 2

На самом деле это не так уж и сложно, использование генератора случайных чисел не так уж и медленно, но если вам очень не повезет, временная сложность станет O(n^2) и в лучшем случае O(1), как вам это нравится?

Однако просто создайте таблицу, которая соединяет двух человек, посмотрите, встречаются ли их идентификаторы, и это быстро, если нет, просто добавьте их идентификаторы, используйте T-SQL, чтобы потерять дополнительные соединения.

Answer 3

Мне кажется, эта проблема уже решена.

1. Вы хотите составлять списки пар.
2. Вам нужны все списки пар (по одному на каждый день)

Для этого вам не нужно использовать случайную функцию.Вам просто нужно сгенерировать все списки пар.

А перестановка Страница в Википедии содержит несколько реализаций алгоритма, которые вам нужно использовать.

#!/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";
}