How do I use randperm to produce a completely new sequence (no numbers in same place)?

Is there a way to permute numbers with randperm and get a completely new permutation every time?

For example,

randperm(5)

to generate multiple rows of 5 numbers, none of which have the same number in the same column?

For example:

 4 2 5 1 3

and

 3 4 1 2 5

NOT

 4 2 5 1 3

and

 3 2 4 5 1

which have the different sequences, but the 2 is in the same location.

[Jan]

Please explain, if you need just 2 index vectors (then the derangment is useful) or a set of all n index vectors with no value appearing twice in a row and column.

Answer 1

[Jan]

Thanks Bruno! Now I see the limitations and the connection to the derangement.

Next approach:

a = mod(bsxfun(@plus, 0:4, transpose(0:4)), 5) + 1;
b = a(randperm(5), :);
b = b(:, randperm(5))

Or simpler:

b = mod(bsxfun(@plus, randperm(5), transpose(randperm(5))), 5) + 1;

Does this now reduce the correlation between neighboring elements to the minimum considering the OPs demands? Jan

[Joseph Kirk]

This is the best answer. It will be fast for any N and it has a very small memory requirement. More importantly, it is not excessively complex and still gives the OP exactly what they asked for.

[Bruno Luong]

This is a way to go for reasonable large n.

Answer 2

[Walter Roberson]

Not directly with randperm(), except perhaps by way of looping and rejecting the ones that do not fit.

Once you have a particular solution, say S, you can generate other solutions isomorphic to it by using

T = randperm(5);
T(S)

I have in mind an idea that might work to generate such matrices, but I have not fleshed it out. Probably someone else will come up with a complete solution before I have time to revisit this.

[Chris]

I am not sure this would work. For example if T comes out as the inverse of S, than T(S) will be the identity, and all elements will be fixed.

Answer 3

[Paulo Silva]

b=randperm(5);t=0;
for a=1:10
    while(1)
        c=randperm(5);
        e=0;
        for d=1:5
            if (ismember(c(d),b(:,d)))
                e=1;
                break
            end
        end
        if (e==0)
            t=0;
            break
        else
            t=t+1;
            if ((t>2000) | (numel(b(:,1)))==5)
                return
            end
        end
    end
    b=[b;c]
end

[Paulo Silva]

It's a brute force method, t is used just to stop the function from infinite looping, it stops when the output got 5 lines but the user might change the number of lines to a greater value than the one possible, it stops after failing 2000 times.

Answer 4

[Matt Fig]

O.k., I see I misread the requirements. You want no two elements to be equal, correct? This should work too, if A is not really large:

function As = mix(A)
T = perms(A);
As = T(1,:);
S = size(T,1);
L = length(A);
P = prod(1:L-1);

for jj =1+P:P:S
    for ii = 0:P-1
        if ~any(bsxfun(@eq,As,T(jj+ii,:)),2)
            As = [As;T(jj+ii,:)];
        end
    end
end

Answer 5

[Matt Fig]

Or, perhaps more efficient even:

function As = mix2(A)
T = A(randperm(length(A))).';
As = zeros(length(A));
As(:,1) = T;
for jj =2:length(A)
   As(:,jj) = circshift(As(:,jj-1),1);
end

Then from the command line:

F = mix2([3 6 7 8 9 12])
F =
     7     3    12     8     6     9
     9     7     3    12     8     6
     6     9     7     3    12     8
     8     6     9     7     3    12
    12     8     6     9     7     3
     3    12     8     6     9     7

The rows of F are your permutations.

Answer 6

[Jan]

A set of completely different permutations of length 5 contains just 5 vectors. For example:

a = randperm(5);
b = bsxfun(@plus, a, transpose(1:5));
R = mod(b, 5) + 1

>> 5 2 3 4 1
   1 3 4 5 2
   2 4 5 1 3
   3 5 1 2 4
   4 1 2 3 5

Then you can choose any lines of this matrix.

[Paulo Silva]

That requires the Financial Toolbox™ because of the plus function.

[Walter Roberson]

No, "plus" is the name of the function that does addition:

+ Plus.

X + Y adds matrices X and Y. X and Y must have the same

dimensions unless one is a scalar (a 1-by-1 matrix).

A scalar can be added to anything.

C = PLUS(A,B) is called for the syntax 'A + B' when A or B is an

object.

Overloaded methods:

timeseries/plus

laurpoly/plus

laurmat/plus

[Paulo Silva]

sorry, my mistake

Answer 7

[Bruno Luong]

Jan's method only concerns circular permutation, which is limited.

In general, any permutation of a set of cardinal n can be decomposed k non overlap cycles. The sum of cardinals of the cycle is n.

OP's request can be translated in term of permutation theory as "all cycle have cardinal > 1" (cycle of cardinal 1 is a fixed point).

Jan's is one realization of, i.e., there is one (k=1) linear cycle of cardinal n.

One can program more generic of all valid permutations by splitting (randomly) the set 1:n in k subsets of cardinal >= 2, then select a (random) circular permutation of each subset.

This decomposition a little cumbersome to code, but it should give a better randomized permutation.

I believe there is a smarter way to do it. There one of the code by JOS in FEX, then name escape me now (something like derangement).

[Jan]

Jos DERANGE disappeared in the last days. There was an earlier version RANDPERMFULL, which replied cyclic permutations by accident only (disappeared also).

But both functions do not match the OPs question: The derangement is a permutation with: not(any(P == 1:length(P))). No element remains at the same position. But the OP asked for two different permutations, which differ in all elements. And if you start with *any* permutation (see RANDPERM in my solution), there are only (n-1) other possible vectors. And the created permutations are only circular, if the reply by RANDPERM is circular.

Note: The permutations in my example are stored in the rows, not in the columns!

[Jan]

See the OPs example: p=[3 4 1 2 5] *is* wanted, although p(5)==5!

[Bruno Luong]

Jan's quote: [...But the OP asked for two different permutations, which differ in all elements...]

Simply apply the derangement on the first permutation.

Both problems are then equivalent.

Bruno

[Jan]

I think the new order of answers is really confusing. Bruno's "Jan's method" concerns my first answer:

a = randperm(5); b = bsxfun(@plus, a, transpose(1:5)); R = mod(b, 5) + 1;

But not my second answer using two RANDPERMs, which is found on top of the answer list now - confusingly.

Answer 8

[Jos (10584)]

I just resubmitted RANDPERMFULL to the FEX. It will be available in few days.

To the OP, should the next permutation be different from the current permutation (i.e., a derangement of the current permutation) only, or should it be different from all previously obtained permutations? In other words, is this sequence of permutations allowed?

[2 3 1 4] -> [3 4 2 1] -> [2 1 3 4] -> [3 2 4 1]

[Jos (10584)]

Here is the link:

http://www.mathworks.com/matlabcentral/fileexchange/30189

Answer 9

[Bruno Luong]

This tool by Derek O'Connor can return efficiently a derangement:

http://www.mathworks.com/matlabcentral/fileexchange/30101-rpg-tools

Use it to get two permutations with zero repeat

n = 10;
a = randperm(n)
b = a(GRDrej(n))
% Check
all(a~=b)

Bruno

Answer 10

[Matt Fig]

You could do this with the PERMS function.

A = [4 2 5 1 3];  % Sample code
T = perms(A);
B = randperm(size(T,1));
% display random permutations of A:
for ii = 1:size(T,1)
    T(B(ii),:)
end

If your A matrix is large enough, you may want to consider my NEXTPERM function on the FEX:

http://www.mathworks.com/matlabcentral/fileexchange/24459-next-combinationpermutation

[Paulo Silva]

that perms is great, didn't know it, thanks

but there's something wrong with that code, I believe that the results aren't the correct ones

[Matt Fig]

I must have missed the part where she said she didn't want to have any two elements in the same place.