## Overview

### Introduction

In many applications, all permutations of a given array need to be generated. While there is a straight-forward recursive algorithm, the approach does waste a lot of stack. An iterative technique is not straight-forward, but is efficient. ( Believe it or not, this was an Amazon-Seattle interview question in 2003)

In this post, I have described the iterative algorithm, and outlined the pseudo-code. The Djikstra paper on which this is based, has a reasonably clear example. Perhaps the notes here may explain a few things that were assumed in the paper.

### References

## Explanation of Approach

### Inversions

Let us define Inversion of a number, as a function

inv(∏,i) = count of numbers to the right of i, that are less than iEg In the permutation < 6, 3, 8, 1, 4, 7, 2, 5 >,inv(∏,4) = 1 ,
since 2 is the only number to the right of 4, less than 4 |

### Bound on the Inversion values

Note that, for any permutation inv(∏,i) < i, for any i

- This is obvious, since we account for only numbers 1, 2, …, i-1 , while looking to the right of i.

### Inversionless Permutation

A permutation of N digits, that has no inversions is a sequence in ascending order

Eg :- The permutation <0,1,2,3> has an inversion of [0,0,0,0] |

### Neighboring Inversions

Two inversions are inversions differ in only one position by a value of one.

Eg :- < 0, 0, 1, 1 > and < 1, 0, 1, 2 >are considered neighboring inversions |

### Neighboring Inversions to Neighboring Permutations

Permutations for Neighbouring inversions can be obtained from one another by swapping exactly one item

- For example

Consider a permutation of the digits 0, 1, 2, 3The permutations corresponding to the Inversion areInversion Permutation
i[0] i[1] i[2] i[3] [ 0, 0, 1, 1 ] corresponds to < 0, 2, 3, 1 > and [ 0, 0, 1, 2 ] corresponds to < 0, 3, 2, 1 > |

- There is also a very simple rule to obtain the second permutation from the first

Since the second inversion is formed by increasing i[3] by 1,the second permutation is formed from the first by– moving the number 3 right by one digit. |

- Note that getting a neighboring permutation is a O(1) operation, that involves swapping one number.

### Gray Codes

Gray Codes are a way to cycle through a set of available values, so that the adjacent rows differ in at-most one digit. (It is used mostly in Boolean Algebra).

- Here, we cycle through the inversions as [ i
_{i}, i_{2}, …, i_{j}] , where i_{j}isthe inversion for number j,- and hence varies from 0 through (j-1)

- For the example of Inversions of size 3
- The inversion sequence according to Gray-Code sequence is as shown below
- Also shown is the permutation corresponding to these inversions

Inversion Permutation[ 0, 0, 0, 0 ] < 0, 1, 2, 3 >[ 0, 0, 0, 1 ] < 0, 1, 3, 2 >
[ 0, 0, 0, 2 ] < 0, 3, 1, 2 > [ 0, 0, 0, 3 ] < 3, 0, 1, 2 > [ 0, 0, 1, 3 ] < 3, 0, 2, 1 > [ 0, 0, 1, 2 ] < 0, 3, 2, 1 > [ 0, 0, 1, 1 ] < 0, 2, 3, 1 > [ 0, 0, 1, 0 ] < 0, 2, 1, 3 > [ 0, 0, 2, 0 ] < 2, 0, 1, 3 > … … |

- Observe carefully how the above permutations obey the rules
- The Gray-Code generation algorithm is described below
- The algorithm needs to distinguish between an increasing sequence of values, and a decreasing sequence of values.
- To encode this, we use positive values when the sequence of values is increasing, and a decreasing set of values, when it is decreasing
- Also, there needs to be a clear distinction between +0 and -0.
- To accommodate this, we add one to all the positive values, and decrement one from the negative values. So, the range becomes –N to -1 ( versus –N+1 to 0 ), and N to 1 ( versus N-1 to 0 )

## The Algorithm

### Gray-Code Generation

So, a sequence of values< 0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 2, 3 >would be encoded as
< 1, 2, 3, 4, -4, -3, -2, -1, 1, 2, 3, 4 > |

- With this encoding, the pseudo-code becomes, as shown above

<next,pos> := get_next_inv(curr,N);// Function to iterate over all digitsfunc get_next_inv( curr:Array, size:int ) : <next:Array,pos:int>
{ int pos = size-1; while(pos > 0) { <next,cont> = iter(curr,pos,size); if (!cont) return <next,pos>; pos–; } return <next,pos>; } // Function to iterate for a single digit func iter( curr:Array, i:pos, size:int ) : tuple<next: Array, carry: bool> if (curr[i] == size ) { curr[i] = -size; return <curr, false>; } curr[i]++; if ( curr[i] == -1 ) { return <curr,true>; } return <curr,false>; } |

### Getting the next Permutation

- Getting the next Permutation involves the following steps

- Compute the inversion array from the current permutation
- Compute the next inversion and the change using the next_gray_code routine mentioned above
- Execute the change on the original permutation, and return the new one.

func next_perm(curr:Array, cinv:Array, size:int): <next:Array, ninv:Array>{
<ninv,pos> = get_next_inv( cinv, size ); next = move_item( curr, pos ); return <next,ninv>; } func move_item( curr:Array, pos:int ): <next:Array> { next = curr; exchange( next, pos, pos + sign(curr[pos]) ); return next; } |

## Leave a Reply