# Permutation Generators

by Bill McKeeman

Efficient permutation generators.

Updated February 26, 2006

## Contents

- New Material
- Specification
- The Permutation Generator
- Function perms(M)
- Function perms(M, 'even') or perms(M, 'odd')
- Function perms(M, 'signs')
- Function perms(M, 'cycles')
- Function perms(M, 'unique')
- Implementation Tricks
- Vector Input Examples
- Matrix Input (more than one input vector)
- The Result gets BIG in a Hurry
- Testing
- Useful Output

## 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