CODEWITHSUNDEEP
algorithmmatlabpermutationrepresentation
ealione
ealione

Reputation: 1636

Index of a permutation

I was recently reading about Lehmer codes and how they can be used to map an index to a permutation corresponding to that index and realized they can be quite useful to quickly generate a permutation. Does anyone know how can this be done using an algorithm, and also what are the limits of such a method, I suppose we can't go above index = 1.7977e+308, but still seems quite an interesting method.

So basically lets say we have

perm
  1   0 0 0
  2   0 0 1
  3   0 0 2
  4   0 1 0
  5   0 1 1
  6   0 1 2
     ...

We should be able to deduce that the index of [ 0 1 0 ] is 4, or that the index 6 corresponds to [ 0 1 2 ]

Thanks for any help.

Upvotes: 2

Views: 171

Answers (1)

RTL
RTL

Reputation: 3587

The vector for each index is the base 3 representation of the index (minus one) the functions dec2base and base2dec can be used for this with a little fiddling to get the sting outputs to the required format

index to vector

index=4; % input index
n=3;     % length of vector 

vec=str2num([dec2base(index-1,3,n)].').'
vec=

     0     1     0

vector to index

vec=[0,1,2]; % input vector
vecstr=strcat(['' vec(:)+'0'].');
index=base2dec(vecstr,3)+1

index =

     6

Upvotes: 6

Related Questions