Перемешать массив при интервале повторяющихся элементов

Question

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

Этот код работает, но мне кажется неэффективным:

function shuffledArr = distShuffle(myArr, myDist)
% this function takes an array myArr and shuffles it, while ensuring that repeating 
% elements are at least myDist elements away from on another    

% flag to indicate whether there are repetitions within myDist
reps = 1;
while reps 

    % set to 0 to break while-loop, will be set to 1 if it doesn't meet condition
    reps = 0;  

    % randomly shuffle array
    shuffledArr = Shuffle(myArr);

    % loop through each unique value, find its position, and calculate the distance to the next occurence
    for x = 1:length(unique(myArr))
        % check if there are any repetitions that are separated by myDist or less
       if any(diff(find(shuffledArr == x)) <= myDist)
           reps = 1;
       break;
   end
end
end

Это кажется мне неоптимальным по трем причинам:

1) Возможно, нет необходимости повторно перемешивать, пока не будет найдено решение.

2) Этот цикл while будет продолжаться вечно, если нет возможного решения (т. Е. Установка myDist слишком высокой, чтобы найти подходящую конфигурацию). Есть идеи, как это уловить заранее?

3) Должен быть более простой способ определить расстояние между повторяющимися элементами в массиве, чем то, что я делал, просматривая каждое уникальное значение.

Буду признателен за ответы на пункты 2 и 3, даже если пункт 1 верен и это можно сделать за один случай.

Answer 1

Если вы просто хотите найти одно из возможных решений, вы можете использовать что-то вроде этого:

x = [1   1   1   2   2   2   3   3   3   3   3   4   5   5   6   7   8   9];
n = numel(x);
dist = 3;           %minimal distance
uni = unique(x);    %get the unique value
his = histc(x,uni); %count the occurence of each element
s = [sortrows([uni;his].',2,'descend'), zeros(length(uni),1)];

xr = [];            %the vector that will contains the solution

%the for loop that will maximize the distance of each element
for ii = 1:n
    s(s(:,3)<0,3) = s(s(:,3)<0,3)+1;
    s(1,3) = s(1,3)-dist;
    s(1,2) = s(1,2)-1; 
    xr = [xr s(1,1)];
    s = sortrows(s,[3,2],{'descend','descend'})
end

if any(s(:,2)~=0)
    fprintf('failed, dist is too big')
end

Результат:

xr = [3   1   2   5   3   1   2   4   3   6   7   8   3   9   5   1   2   3]

Explaination:

Я создаю вектор s и в начале s равен:

s =

   3   5   0
   1   3   0
   2   3   0
   5   2   0
   4   1   0
   6   1   0
   7   1   0
   8   1   0
   9   1   0

%col1 = unique element; col2 = occurence of each element, col3 = penalities

На каждой итерации нашего цикла for мы выбираем элемент с максимальным вхождением, поскольку этот элемент будет сложнее разместить в нашем массиве.

Тогда после первой итерации s будет равно:

s =

   1   3   0  %1 is the next element that will be placed in our array.
   2   3   0
   5   2   0
   4   1   0
   6   1   0
   7   1   0
   8   1   0
   9   1   0
   3   4  -3  %3 has now 5-1 = 4 occurence and a penalities of -3 so it won't show up the next 3 iterations.

в конце каждого числа второго столбца должно быть равно 0, если это не минимальное расстояние было слишком большим.

Answer 2

Я думаю, что достаточно проверить следующее условие, чтобы предотвратить бесконечные циклы:

[~,num, C] = mode(myArr);
N = numel(C);
assert( (myDist<=N)  || (myDist-N+1) * (num-1) +N*num <= numel(myArr),...
'Shuffling impossible!');

Предположим, что myDist равно 2, и у нас есть следующие данные:

[4 6 5 1 6 7 4 6]

Мы можем найти режим, 6, с его появлением, 3.Мы организуем 6 s, разделяя их на 2 = myDist пробелы:

6 _ _ 6 _ _6

Для заполнения пробелов должно быть (3-1) * myDist = 4 чисел.Теперь у нас есть еще пять чисел, поэтому массив можно перемешать.

Проблема становится более сложной, если у нас несколько режимов.Например, для этого массива [4 6 5 1 6 7 4 6 4] у нас есть режимы N=2: 6 и 4.Они могут быть расположены следующим образом:

6 4 _ 6 4 _ 6 4 

У нас есть 2 пробела и еще три числа [ 5 1 7], которые можно использовать для заполнения пробелов.Например, если бы у нас было только одно число [ 5], было бы невозможно заполнить пробелы и мы не могли бы перемешать массив.

Для третьего пункта вы можете использовать разреженную матрицу для ускорения вычислений (мое первоначальное тестирование в Octave показывает, что оно более эффективно):

function shuffledArr = distShuffleSparse(myArr, myDist)
    [U,~,idx] = unique(myArr);
    reps = true;
    while reps 
        S = Shuffle(idx);
        shuffledBin = sparse ( 1:numel(idx), S, true, numel(idx) + myDist, numel(U) );
        reps = any (diff(find(shuffledBin)) <= myDist);
    end
    shuffledArr = U(S);
end

В качестве альтернативы вы можете использовать sub2ind и сортировка вместо разреженной матрицы:

function shuffledArr = distShuffleSparse(myArr, myDist)
    [U,~,idx] = unique(myArr);
    reps = true;
    while reps 
        S = Shuffle(idx);
        f = sub2ind ( [numel(idx) + myDist, numel(U)] , 1:numel(idx), S );
        reps = any (diff(sort(f)) <= myDist);
    end
    shuffledArr = U(S);
end