MATLAB Answers

Random shuffle vector such that all elements fall in new index positions

8 ビュー (過去 30 日間)
Javier Agustin Romero
Javier Agustin Romero 2019 年 11 月 29 日
Commented: Javier Agustin Romero 2019 年 11 月 29 日
Hello community. The title is quite self explanatory. Suppose I have the vector:
v = [1 2 3 4 5 6 7]
I want to shuffle the elements of v such that there is no index repetition with previous order. For example, this is not good
6 5 3 1 7 2 4
because '3' falls in the same place as before. This is good:
7 6 2 1 4 5 3
I am performing the shuffling with:
v(randperm(length(v)))
Of course this is just an example, I will be working with quite large arrays, so jumping into for or while loops to check weather new permutation is ok or not (and make new permutation if so) is time consuming. Any ideas or suggestions will be much appreciated. Cheers.

  0 件のコメント

サインイン to comment.

採用された回答

Stephen Cobeldick
Stephen Cobeldick 2019 年 11 月 29 日
編集済み: Stephen Cobeldick 2019 年 11 月 29 日
What you describe is called a derangement.
You can download FEX submissions that perform derangements, e.g.:
Note that Jan's submission uses a mex function, and will be quite efficient on your large arrays.

  1 件のコメント

Javier Agustin Romero
Javier Agustin Romero 2019 年 11 月 29 日
I didn't know this type of permutation was called a derangement, so thank you for that.
And Jan's function works amazingly well.
I will crown your answer as the accepted one, but I thank everyone who contributed to this thread.

サインイン to comment.

More Answers (2)

Stijn Haenen
Stijn Haenen 2019 年 11 月 29 日
Try this:
v=[1:100]; %your vector
List=1:numel(v);
for i=1:numel(v)
newList=List;
newList(i)=[];
newpos=datasample(newList(newList>0),1);
List(newpos)=0;
newVector(newpos)=v(i);
end

  1 件のコメント

Guillaume
Guillaume 2019 年 11 月 29 日
An explanation of why it works, or even better some comments to the code would be useful.
In particular, I don't see how your code guarantees that when your reach index 100 the only index left to pick is not 100. For example, if datasample returned the sequence [2:99, 1] on the last step of the loop, the only index left to pick is 100. Your code would simply discard it and return a new vector with one less element

サインイン to comment.


Guillaume
Guillaume 2019 年 11 月 29 日
編集済み: Guillaume 2019 年 11 月 29 日
I would:
  • do a normal randperm that may map some elements back to their original location
  • any element that has been mapped to its original location, swap it with any other element, guaranteeing you that the two swapped elements are not at their original location
v = 1:2000; %demo vector. Can have duplicate values
neworder = randperm(numel(v)); %may result in some indices mapping to themselves
hasnotmoved = find(neworder == 1:numel(v), 1); %is there any index that has mapped to itself. If so pick the first one
while hasnotmoved %go over them one by one
available = [1:hasnotmoved-1, hasnotmoved+1:numel(v)]; %list of indices other than the one that did not move
swapwith = available(randi(numel(v)-1)); %choose one index at random other than it
neworder([swapwith, hasnotmoved]) = [hasnotmoved, swapwith]; %and swap the two
hasnotmoved = find(neworder == 1:numel(v), 1); %any more?
end
%now we're guaranteed that no index mapped to itself
assert(all(neworder ~= 1:numel(v)), 'Did not work!')
newv = v(neworder);
In the majority of cases there's very few elements that mapped back to each other, so the while loop will do very few iterations. Worst case scenario, randperm did not swap anything and the while loop swaps all elements one by one.
edit: initial implementation was slightly flawed

  2 件のコメント

Stephen Cobeldick
Stephen Cobeldick 2019 年 11 月 29 日
"...guaranteeing you that the two swapped elements are not at their original location"
How?
What stops an element from being moved back to its original location?
Guillaume
Guillaume 2019 年 11 月 29 日
If you have the sequence
........P.......N......
where index of N is N, and index of P is Q (where Q may or may not be equal to P, doesn't matter), if you swap P and N:
........N.......P......
then index of N is now Q, with , and index of P is now N, with
edit: however there is a flaw in the way I've implemented the algorithm in that I may pick a Q that is an element that is going to be swapped later by the loop and is thus no longer the hasnotmoved element it was. A while loop instead of the for loop will fix that (and will have less than or the same number of iterations as the for loop).

サインイン to comment.

サインイン してこの質問に回答します。

製品


リリース

R2018b

Translated by