Shuffle vector with constraints

Question

Pieter 2014-1-14

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/112353-shuffle-vector-with-constraints

回答： Pieter 2014-1-14

Hi,

I have an array of 50 1's, 50 2's, etc up to 50 8's. I would like to shuffle them with the constraint that two consecutive numbers cannot be the same. I tried several options but most are very cpu intensive or did not yield a good result. Are there computation efficient solutions to this problem?

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Azzi Abdelmalek 2014-1-14

This is not enough as information. Because you can set them for example [1 2 3 1 2 3 1 2 3 . . .]

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

W. Owen Brimijoin 2014-1-14

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/112353-shuffle-vector-with-constraints#answer_120862

在 MATLAB Online 中打开

A brute force method works fairly well in this scenario - 1) start with a shuffled version of the sequence, 2) find repeats, 3) swap any repeats to different locations... goto 2 (rinse and repeat). This sort of method would likely be terrible if you had fewer characters in your sequence, but for nine unique elements, it seems to halt very quickly.

Making your sequence:

seq = repmat([1:8],50,1); %make sequence
seq = [seq(:);repmat(9,30,1)]; %make sequence

Doing the reshuffling:

seq = seq(randperm(numel(seq))); %initial shuffle
old_idx= unique(find(diff(seq)==0));%find repeats
while ~isempty(old_idx), %continue until no repeats
    new_idx = unique(setdiff([1:length(seq)],old_idx)); %find new spots
    new_idx = new_idx((randi(length(new_idx),length(old_idx),1)))';
    seq([new_idx;old_idx],:) = seq([old_idx;new_idx],:); %swap
    old_idx= unique(find(diff(seq)==0));%find repeats
end

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Mischa Kim 2014-1-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/112353-shuffle-vector-with-constraints#answer_120853

编辑：Mischa Kim 2014-1-14

在 MATLAB Online 中打开

Since I do not know what techniques you have tried, here's (another) one? Start with sorting the 1's, 2's, etc. in matrix form, i.e.,

1 1 1...
2 2 2...
3 3 3...

and perform permutations on the individual columns (e.g using randperm). Based on the entry of the last row in the first column randomly pick a column vector with a different first row entry and make it the new second column. Using this process work your way through all the columns (you might have to do some more permutations towards the final columns). Once done, transpose and concenate all of the column vectors.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 3

Pieter 2014-1-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/112353-shuffle-vector-with-constraints#answer_120854

Hi Mischa,

Thanks, this is a very good suggestion for one of my other experiments. This however has two issues I think:

1) It is not a constraint that every subvector of 8 numbers is a permutation. The only constraint is that no two consecutive numbers are the same.

2) This only works if all numbers occur equally. I forgot to mention that we have in fact 9 numbers. 1 to 8 occur 50 times, 9 occurs only 30 times.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Mischa Kim 2014-1-14

编辑：Mischa Kim 2014-1-14

Hello Pieter,

Understood. I used the permutation for shuffling with a certain level of randomness (while satisfying the constraint).
You can still use the approach outlined above by randomly tossing in the 30 9's into the vector at the end.

请先登录，再进行评论。