MATLAB Examples

Permutation Generators

by Bill McKeeman

Efficient permutation generators.

Updated February 26, 2006

Contents

New Material

  • Complete rework. What is presented below is a compatible extension of MATLAB perms.

Specification

Given a set of input vector (mXn matrix), generate...

  • all the rearrangements of the values,
  • as above, but restricted to even or odd permutations,
  • all the signed values of the data,
  • all end-around shifts of the values,
  • all meaningful combinations of the above,
  • all unique results of the above, and
  • preserve the class of the input.

Some readers will want to skip ahead to the examples below.

The Permutation Generator

  • perms(M,flags)

This proposed replacement for MATLAB perms is more general but uses the central idea for generating permutations. The input is a matrix which contains a set of vectors, each of which gets permuted independently. Suppose that [m,n] = size(M) in the following paragraphs.

Function perms(M)

There are factorial(n) unique permutations of the vector 1:n.

One can permute any vector of values (not necessarily 1:n). If the input values are all different, the resulting set of vectors is of maximal size (that is, factorial(n)). If there are repeated values, then perms with flag unique generates fewer vectors.

A simple view of the method for generating all permutations of a vector v of length n is to generate all permutations p=perms(1:n) first, then report v(p). If the input is actually a matrix (more than one original vector), then the algorithm is applied separately to each vector and the results are catenated. If there are repeated values in the input, there may be repeated results.

Function perms(M, 'even') or perms(M, 'odd')

Exactly 1/2 of the permutations of 1:n are even, and 1/2 of them are odd. One can think of this as the number of interchanges a sort routine would have to make to restore the permutation to ascending order. The original sequence 1:n is an even permutation (it take 0 exchanges to order it). Or one could use 2 exchanges. But never an odd number (group theory result).

Function perms(M, 'signs')

If the input has no zero values, there are exactly m*2^n results differing only in the sign of the values. Since the final size is known, one can replicate the input matrix then systematically change the signs of the replicated data in place. If there are zeros in M there may be repeated vectors in the result.

Function perms(M, 'cycles')

There are at most n cyclical permutations of a vector of length n.

Function perms(M, 'unique')

if the unique flag is added to one of the calls above, MATLAB function unique(M, 'rows') is used to remove duplicate values. Flag unique is somewhat expensive, so should be avoided unless necessary.

Implementation Tricks

Making the result by in-place modification of data is more efficient than constructing the data in bits and pieces for final assembly. Nested functions make this convenient. The in-place data is a local variable of the outer function. Nested functions access and modify the data. The outer function reports the result. (As a matter of interest, two levels of nesting are used in perms.)

For function perms, the computation of the 1:n permutations is repeated each time perms is called. I experimented with saving the base permutations but in fact the time saving was not significant and the persistent storage cost was high. This should probably be looked into again because it is so counterintuitive. One also should zap any results after they are used so they do not hang around using memory.

format compact

Vector Input Examples

A few small examples suffice to make the meaning of the functions clear.

perms(int8(1:3))
ans =
    3    2    1
    3    1    2
    1    2    3
    1    3    2
    2    3    1
    2    1    3
perms(1:3, 'cycles')
ans =
     1     2     3
     3     1     2
     2     3     1
perms([1 1 1], 'signs')
ans =
    -1    -1    -1
    -1    -1     1
    -1     1    -1
    -1     1     1
     1    -1    -1
     1    -1     1
     1     1    -1
     1     1     1
perms([1 0 0]/2, 'cycles')
ans =
    0.5000         0         0
         0    0.5000         0
         0         0    0.5000
perms([1 1 0 0]/3, 'unique')
ans =
         0         0    0.3333    0.3333
         0    0.3333         0    0.3333
         0    0.3333    0.3333         0
    0.3333         0         0    0.3333
    0.3333         0    0.3333         0
    0.3333    0.3333         0         0
perms([2 1 0]/sqrt(2), 'signs', 'unique')
ans =
   -1.4142   -0.7071         0
   -1.4142    0.7071         0
    1.4142   -0.7071         0
    1.4142    0.7071         0
perms('abc', 'even')
ans =
cab
abc
bca

It is perhaps surprising that all the next three give the same result.

perms([1 1], 'all', 'unique')
perms([1 1], 'even', 'unique')
perms([1 1], 'odd', 'unique')
ans =
     1     1
ans =
     1     1
ans =
     1     1
perms(sparse(eye(5)), 'unique')
ans =
   (5,1)        1
   (4,2)        1
   (3,3)        1
   (2,4)        1
   (1,5)        1

Matrix Input (more than one input vector)

perms([1:3; 1 0 0], 'unique')
ans =
     0     0     1
     0     1     0
     1     0     0
     1     2     3
     1     3     2
     2     1     3
     2     3     1
     3     1     2
     3     2     1
perms(single([0:1/3:2/3; 3+i 0 0]), 'signs', 'unique')
ans =
        0             0.3333             0.6667          
        0             0.3333            -0.6667          
        0            -0.3333             0.6667          
        0            -0.3333            -0.6667          
  -3.0000 - 1.0000i        0                  0          
   3.0000 + 1.0000i        0                  0          

The Result gets BIG in a Hurry

The flags work together. The following line is equivalent to

perms(perms(int8(1:3)),'signs')

perms(int8(1:3), 'all', 'signs')
ans =
   -3   -2   -1
   -3   -2    1
   -3    2   -1
   -3    2    1
    3   -2   -1
    3   -2    1
    3    2   -1
    3    2    1
   -3   -1   -2
   -3   -1    2
   -3    1   -2
   -3    1    2
    3   -1   -2
    3   -1    2
    3    1   -2
    3    1    2
   -1   -2   -3
   -1   -2    3
   -1    2   -3
   -1    2    3
    1   -2   -3
    1   -2    3
    1    2   -3
    1    2    3
   -1   -3   -2
   -1   -3    2
   -1    3   -2
   -1    3    2
    1   -3   -2
    1   -3    2
    1    3   -2
    1    3    2
   -2   -3   -1
   -2   -3    1
   -2    3   -1
   -2    3    1
    2   -3   -1
    2   -3    1
    2    3   -1
    2    3    1
   -2   -1   -3
   -2   -1    3
   -2    1   -3
   -2    1    3
    2   -1   -3
    2   -1    3
    2    1   -3
    2    1    3

Testing

I have a test suite that tries and checks 328 combinations.

Useful Output

So, what good are permutation generators? See my geometrical figure sharedemo for an extended example. You can also read the LEGO proposal.

bill = imread('BillMathWorks03.jpg'); image(bill);
set(gca, 'outerposition', [0,0,.4,.9])
axis equal; axis off