Генерация нескольких последовательностей чисел с уникальными значениями в каждом индексе

Question

У меня есть строка с номерами 1:n.Я хочу добавить вторую строку также с номерами 1:n, но они должны быть в случайном порядке, удовлетворяя следующим требованиям:

1. Нет позиций с одинаковыми номерами в обеих строках
2. Двойная комбинация чисел не встречается

Например, в следующих

Row 1:  1  2  3  4  5  6  7 ...
Row 2:  3  6  15 8  13 12 7 ...  

число 7 находится в одной и той же позиции в обеих строках 1 и 2 (а именно в позиции7, тем самым не удовлетворяя правилу 1)

, в то время как в следующем

Row 1:  1  2  3  4  5  6  7 ...
Row 2:  3  7  15 8  13 12 2 ...

комбинация 2 + 7 появляется дважды (в позициях 2 и 7; таким образом, не удовлетворяя правилу 2).

Возможно, было бы возможно - но неоправданно много времени - сделать это вручную (по крайней мере, до разумного числа), но в MATLAB должно быть довольно элегантное решение для этого.

Answer 1

Эта проблема называется разложением перестановки.
Используйте функцию randperm , чтобы найти случайную перестановку ваших данных.

x = [1  2  3  4  5  6  7];
y = randperm(x);

Затем вы можете проверить правильность последовательности. Если нет, делайте это снова и снова ..
У вас есть вероятность около 0,3 каждый раз, чтобы добиться успеха, что означает, что вам нужно примерно 10/3 раза, чтобы попытаться, пока не найдете его. Поэтому вы найдете ответ очень быстро.

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

Редактировать

Если вы хотите иметь только циклы размером> 2, это обобщение проблемы. В нем написано, что вероятность в этот случай меньше, но достаточно велик, чтобы найти его за фиксированное количество шагов. Таким образом, тот же подход остается в силе.

Answer 2

Андрей уже указал вам на randperm и подход, подобный отбраковке. После генерации перестановки p простой способ проверить, имеет ли она фиксированную точку, - any(p==1:n). Простой способ проверить, содержит ли он циклы длины 2: any(p(p)==1:n).

Таким образом, получаются перестановки p из 1:n, удовлетворяющие вашим требованиям:

p=[];
while (isempty(p))
    p=randperm(n);
    if any(p==1:n), p=[]; 
    elseif any(p(p)==1:n), p=[]; 
    end
end

Окружая это циклом for и для каждого подсчета итераций цикла while, кажется, что нужно генерировать в среднем 4.5 перестановок для каждой "действительной" (и 6.2, если циклы длины три также не допускаются). Очень интересно.

Answer 3

Это довольно просто. Создайте случайную перестановку узлов, но интерпретируйте список следующим образом: интерпретируйте его как случайный обход узлов, и если узел «b» появляется после узла «a», это означает, что узел «b» появляется ниже узла «a». в списках:

Итак, если ваша начальная случайная перестановка равна

3 2 5 1 4

Тогда обход в этом случае 3 -> 2 -> 5 -> 1 -> 4, и вы создаете строки следующим образом:

Row 1:  1 2 3 4 5
Row 2:  4 5 2 3 1

Эта случайная прогулка удовлетворит оба условия.

Но вы хотите разрешить более одного цикла в вашей сети? Я знаю, что вы не хотите, чтобы два человека носили шляпы друг друга. Но как насчет 7 человек, у которых 3 есть шляпы друг друга, а у других 4 шляпы друг друга? Это приемлемо и / или желательно?