Перестановка n элементов путем замены каждого элемента не более чем на k позиций

У меня есть вектор (n = 4 в примере):

x = '0123';

Мне нужен вектор y того же размера, что и x, и с теми же элементами, что и в x, в другом порядке:

y = ['0123'; '0132'; '0213'; '0231'; '0312'; '0321'; '1023'; '1032'; '1203'; '1302'; '2013'; '2031'; '2103'; '2301'];
y(ceil(rand * numel(y(:, 1))), :)

то есть такая перестановка, что каждому элементу в y разрешено случайным образом изменять не более чем k позиций по отношению к его исходной позиции в x (k = 2 в примере). Распределение вероятностей должно быть однородным (т. е. каждая перестановка должна произойти с одинаковой вероятностью).

Очевидный, но неэффективный способ сделать это, конечно, найти случайную неограниченную перестановку и проверить постфактум, происходит ли это с соблюдением ограничения. Для небольших векторов вы можете найти все перестановки, удалить те, которые не разрешены, и случайным образом выбрать среди оставшихся. Любая идея о том, как сделать то же самое более эффективно, например, заменив элементы местами?


matlab permutation constraint-programming
person randomatlabuser    schedule 10.02.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я не вижу другого подхода, кроме метода отказа, который вы упомянули. Однако вместо того, чтобы перечислять все разрешенные перестановки, а затем выбирать одну, более эффективно избегать этого списка. Таким образом, вы можете случайным образом сгенерировать перестановку, проверить, действительна ли она, и повторить, если это не так:

x = '0123';
k = 2;

n = numel(x);
done = 0;
while ~done
    perm = randperm(n);
    done = all( abs(perm-(1:n)) <= k ); %// check condition
end
y = x(perm);
person Luis Mendo    schedule 10.02.2014
comment
Спасибо, Луис, кажется, на данный момент это лучший способ сделать это. Если n мало, вероятно, создание списка разрешенных перестановок будет быстрее. - person randomatlabuser; 11.02.2014
comment
Добро пожаловать! Кроме того, создание всего списка может быть лучше, если вы собираетесь генерировать много перестановок. - person Luis Mendo; 11.02.2014

arrow_upward
3
arrow_downward

Генерация всех перестановок может быть легко выполнена с помощью программирования ограничений. Вот короткая модель с использованием MiniZinc для приведенного выше примера (обратите внимание, что мы предполагаем, что здесь x будет содержать n различных значений ):

include "globals.mzn";

int: k = 2;
int: n = 4;
array[1..n] of int: x = [0, 1, 2, 3];
array[1..n] of var int: y;

constraint forall(i in 1..n) (
    y[i] in {x[i + offset] | offset in -min(k, i-1)..min(k, n-i)}
  );

constraint all_different(y);

solve :: int_search(y, input_order, indomain_min, complete)
  satisfy;

output [show(y)];

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

Если вам нужно эффективно генерировать случайную перестановку вашего типа, я думаю, что было бы возможно изменить стандартную перетасовка Фишера-Йейтса для прямой обработки. Стандартный алгоритм использует оставшуюся часть массива для выбора следующего значения и выбирает значение с равномерным распределением вероятностей. Должна быть возможность вести список только действительных на данный момент выборов и изменять распределение вероятностей значений, чтобы оно соответствовало желаемому результату.

person Zayenz    schedule 11.02.2014