How to generate all possible permutations without using the function perms/randperm?

Hello

I am trying to generate all possible permutations (permMat) of a matrix, say A = [1:4], without using the function perms as that is not allowed, but I am stuck.

So far I have came up with

while size(permMat,1) ~= factorial(4)
               %to find a random permutation of A          
               while length(r3)~= 4 %where r3 is a random permutation of A 
                        x=randi([1,C]);
                        if sum(r3==x)==0
                            r3=[r3 x];
                        end
                    end

                          permMat = [permMat;r3];
                          permMat = unique(permMat,'rows');

                  end

However, I realised that using this above method to find a random permutation will only result in the same permutation in the loop. Is there anyway to generate a always-changing random permutation in the loop? Or is there a better way to generate all possible permutations?

Thanks!

Answer 1

[John D'Errico]

Using random permutations to try to generate all possible permutations is simply insane. Sorry, but you will never be happy with that approach. Even for small sets of elements this will be terribly inefficient.

You can simply generate all possible permutations using a recursive scheme, given a vector v of elements, where v is not too long. For a vector of length n, there will be factorial(n) permutations, so if n is greater than about 10 or so, ANY scheme will take some effort.

function P = myperms(v)
% simple recursive scheme to generate all permutations of a vector v.
n = numel(v);
if n <= 1
  P = v;
else
  P = zeros(factorial(n),n);
  f = factorial(n-1);
  L = 1:f;
  for ii = n:-1:1
    P(L,1) = v(ii);
    P(L,2:n) = myperms(v(setdiff(1:n,ii)));
    L = L + f;
  end
end

As you can see, it works.

myperms([2 3 5])
ans =
     5     3     2
     5     2     3
     3     5     2
     3     2     5
     2     5     3
     2     3     5

perms([2 3 5])
ans =
     5     3     2
     5     2     3
     3     5     2
     3     2     5
     2     5     3
     2     3     5

Same set of permutations, even in the same order.

[Jaye Lee]

Thank you very much! I didn't think of that.