Эффективное генерирование уникальных пар целых чисел

Ответ 1

Легкий, peasy, если смотреть соответствующим образом.

Вы хотите сгенерировать n пар целых чисел [p, q], таких, что p и q лежат в интервале [1, m], а p

Сколько существует пары? Общее число пар равно m * (m-1)/2. (I.e., сумма чисел от 1 до m-1.)

Таким образом, мы могли бы генерировать n случайных целых чисел в диапазоне [1, m * (m-1)/2]. Randperm делает это красиво. (Более старые выпуски matlab не позволяют второму аргументу randperm.)

k = randperm(m/2*(m-1),n);

(Обратите внимание, что я написал это выражение с m забавным способом, разделив на 2 в, возможно, странном месте. Это позволяет избежать проблем точности для некоторых значений m вблизи верхних пределов.)

Теперь, если мы сопоставляем каждую возможную пару [p, q] с одним из целых чисел в k, мы можем работать назад, от целых чисел, порожденных в k, до пары [p, q]. Таким образом, первые несколько пар в этом списке:

{[1,2], [1,3], [2,3], [1,4], [2,4], [3,4], ..., [m-1,m]}

Мы можем рассматривать их как элементы в строго верхнем треугольном массиве размера m по m, таким образом, эти элементы над главной диагональю.

q = floor(sqrt(8*(k-1) + 1)/2 + 1/2);
p = k - q.*(q-1)/2;

Посмотрите, что эти формулы восстанавливают p и q из развернутых элементов в k. Мы можем убедить себя, что это действительно работает, но, возможно, простой способ - это просто тест:

k = 1:21;
q = floor(sqrt(8*(k-1) + 1)/2 + 3/2);
p = k - (q-1).*(q-2)/2;
[k;p;q]'

ans =
     1     1     2
     2     1     3
     3     2     3
     4     1     4
     5     2     4
     6     3     4
     7     1     5
     8     2     5
     9     3     5
    10     4     5
    11     1     6
    12     2     6
    13     3     6
    14     4     6
    15     5     6
    16     1     7
    17     2     7
    18     3     7
    19     4     7
    20     5     7
    21     6     7

Другой способ тестирования - показать, что все пары генерируются для небольшого случая.

m = 5;
n = 10;
k = randperm(m/2*(m-1),n);
q = floor(sqrt(8*(k-1) + 1)/2 + 3/2);
p = k - (q-1).*(q-2)/2;

sortrows([p;q]',[2 1])
ans =
     1     2
     1     3
     2     3
     1     4
     2     4
     3     4
     1     5
     2     5
     3     5
     4     5

Да, похоже, все работает отлично. Теперь попробуйте его для некоторых больших чисел для m и n, чтобы проверить время.

tic
m = 1e6;
n = 100000;
k = randperm(m/2*(m-1),n);
q = floor(sqrt(8*(k-1) + 1)/2 + 3/2);
p = k - (q-1).*(q-2)/2;
toc

Elapsed time is 0.014689 seconds.

Эта схема будет работать на m размером примерно 1e8, прежде чем она будет терпеть неудачу из-за ошибок точности в двойной точности. Точный предел должен быть m не больше 134217728, прежде чем m/2 * (m-1) превысит 2 ^ 53. Хорошей особенностью является то, что не требуется отклонение для повторных пар.

Ответ 2

Это скорее общий подход, а не решение матрицы.

Как насчет того, что вы делаете следующее сначала, вы заполняете вектор следующим образом.

x[n] = rand()
x[n + 1] = x[n] + rand() %% where rand can be equal to 0.

Затем вы снова выполните следующее

x[n][y] = x[n][y] + rand() + 1

И если

x[n] == x[n+1]

Вы должны убедиться, что та же пара еще не выбрана.

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

Этот подход даст вам всю возможность или две целые пары, и он работает в O (n), где n - высота матрицы.

Ответ 3

Следующий код делает то, что вам нужно:

n = 10000;
m = 500;
my_list = unique(sort(round(rand(n,2)*m),2),'rows');
my_list = my_list(find((my_list(:,1)==my_list(:,2))==0),:);
%temp = my_list;    %In case you want to check what you initially generated.
while(size(my_list,1)~=n)
    %my_list = unique([my_list;sort(round(rand(1,2)*m),2)],'rows');
    %Changed as per @jucestain suggestion.
    my_list = unique([my_list;sort(round(rand((n-size(my_list,1)),2)*m),2)],'rows');
    my_list = my_list(find((my_list(:,1)==my_list(:,2))==0),:);
end