Crisp Reading Notes on Latest Technology Trends and Basics

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 [ ii, i2, …, ij ] , where ijisthe 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
  1. Compute the inversion array from the current permutation
  2. Compute the next inversion and the change using the next_gray_code routine mentioned above
  3. 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;

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: