Permutation without using perms, randperm, randsample

I need to write a matlab function to receive an integer (n) and then have a vector for 1:n in a random order. I need to do this without using perms, randperm, or randsample. I have this code:

 function output=permutation(n)
array=1:n;
size_a=size(array);
size_a=size_a(2);
for i=1:size_a
d=randi(numel(array));
newArray(i)=d;
      if find(newArray(i))==d
        d=randi(numel(array));
        newArray(i)=d;
      end
end
    output=newArray
end

I just can't figure out how to get it to not repeat values.

Answer 1

[Roger Stafford]

The logic in your 'if' part is faulty. When you do the test "find(newArray(i))==d", you are doing a test on a single-element vector and the answer would always be 1. Testing whether d==1 is meaningless, and in any case in your subsequent replacement if the 'if' turns out to be true there is no guarantee that you will not later place the same 'd' in another position in 'newArray'.

To make your basic strategy work properly, you need to pick out elements one-at-a-time, as you are doing, and place them in random positions in newArray but keep reducing the available locations in newArray so that no other value gets placed there. In other words, you need an array which keeps shrinking in size, of all the available locations in newArray. You can make use of the [] operation for this. That way you can avoid overwriting previous entries into 'new'Array'.

It pains me to see the problem done in this way, however. It is much more efficient to do as Mathworks has done, to provide n random numbers from 'rand' and sort them using 'sort'. The associated permutation would give you the desired result. However, if this is homework, your teacher might object to this.

[Roger Stafford]

Suppose at one point you have available the following locations in newArray: p = [2,3,5,7] and you have just randomly selected the third position in p "d = randi(length(p))-->3" for placing another value into 'newArray'. Then do this:

newArray(p(d)) = i;   <-- Corrected
p(d) = [];

Then p would read: [2,3,7] and subsequent insertions could not overwrite at location 5 of newArray.

[Image Analyst]

I also thought of Roger's simple way of using rand() and then sort(), rather than your complicated way. It sounds like a homework problem so I'll let you think about it for a little bit. Really, it's not hard for a smart engineer like you. Be sure to look at all the variables that sort() returns.

Answer 2

[Walter Roberson]

You can use ismember to test to see if d is already in the array.