在重复元素间隔时随机播放数组

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)如果没有可能的解决方案(即设置myDist太高而无法找到适合的配置),此while循环将永远继续.有关如何提前发现这一点的任何想法？

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]

说明：

我创建一个向量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。