Apparent error in Matlab's perms function

Question

 p = perms([0:2])

p =

 2     1     0
 2     0     1
 1     2     0
 1     0     2
 0     1     2
 0     2     1

This function is supposed to display the permutations of a vector in reverse lexicographical order. Hence, I would expect the last row of this output to contain the elements 0 1 2; however, it contains 0 2 1. The other rows are displayed correctly.

In short, the order of the last two rows are interchanged. What is going on here?

Answer 1

Yes, this seems to be a bug. Good catch! But probably a bug in the documentation, rather than in the function.

If you type open perms to see the source code, you'll see the following description in the first lines:

%PERMS  All possible permutations.
%   PERMS(1:N), or PERMS(V) where V is a vector of length N, creates a
%   matrix with N! rows and N columns containing all possible
%   permutations of the N elements.
%
%   This function is only practical for situations where N is less
%   than about 10 (for N=11, the output takes over 3 gigabytes).
%
%   Class support for input V:
%      float: double, single
%      integer: uint8, int8, uint16, int16, uint32, int32, uint64, int64
%      logical, char

in which no reference is made to reverse lexicographical order.

The actual job is done by the recursive, local function permsr. If you look at its code, it's not obvious at first how it works (as usual with recursion), but the line

t(t == i) = n

gives a clue that no particular order is sought in the result.

If you try a larger vector you'll see discrepancies from reverse lexicographical order in more rows:

>> perms(0:3)
ans =
     3     2     1     0
     3     2     0     1
     3     1     2     0
     3     1     0     2
     3     0     1     2
     3     0     2     1   %// here. Affects cols 1 and 2
     2     3     1     0
     2     3     0     1
     2     1     3     0
     2     1     0     3
     2     0     1     3
     2     0     3     1   %// here. Affects cols 1 and 2
     1     2     3     0
     1     2     0     3
     1     3     2     0   %// here. Affects cols 2 and 3
     ...

In summary, the function seems to have been designed without regard to any order. It is the documentation which is probably wrong in claiming that order.