A failure (on my part) to pay close attention to the requirements of the first problem meant I implemented an algorithm with a complexity of

`O(n! * n!)`

, which means 25 401 600 iterations for `n = 7`

(sort of reasonable) but **1 625 702 400 iterations**for

`n = 8`

, something my laptop wouldn't be able to finish in any reasonable amount of time. It's much worse when you consider that **n was expected to go as high as 800**! Once I read that, it occurred to me that I had been going at it entirely the wrong way... About

*an hour-and-a-half of going the wrong way*, which involved implementing (and debugging) a nice "permute the items of this list" method.

You see, there was a trick to the problem. Once I realized this, I replaced the double permutation loop with two calls to Sort() and a single

`O(n)`

loop. D'oh! My solution to the small input was judged as correct, so I proceeded to the large input. It ran just as fast and so I submitted its output, too. Well, again, I screwed up with the requirements and it turns out my math was overflowing left, right and center and thus, when the contest ended, I got a measly 5 points (out of a possible 15 for that problem and out of a possible 100 for all 3 problems!), which means I ranked 2363 out of 2394. (you don't find out if your submission to the large version is correct until the end of the contest - I also only attempted the first problem)Oh, well... I might try again in Round 1C (Sunday at 05:00 local time!), but in the meantime I thought I'd publish some of the source code that came out of this. I used Visual Studio 2008, which meant I could try out the neat features of the C# that came out with .NET 3.5, such as:

- the
`var`

keyword - extension methods
- LINQ

OK, so I didn't need to use LINQ, nor did I use extension methods until

*after*the contest, but here's my touched-up

`Permutations`

iterator method, generalized to any `IList<T>`

instance:public static class Extension {

public static IEnumerable<IList<T>> Permutations<T> ( this IList<T> input ) {

int numElements = input.Count;

var slotOffsets = new int[numElements];

var slotBusy = new bool[numElements];

bool allDone = false;

while ( !allDone ) {

#region Set slotBusy flags to false

for ( int i = 0; i < numElements; i++ ) {

slotBusy[i] = false;

}

#endregion

IList<T> permutation = new List<T> ( numElements );

int lastSelected = -1;

for ( int i = 0; i < numElements; i++ ) {

for ( int j = 0; j < numElements; j++ ) {

int selectedSlot = ( lastSelected + 1 + j + slotOffsets[i] ) % numElements;

if ( !slotBusy[selectedSlot] ) {

slotBusy[selectedSlot] = true;

permutation.Add ( input[selectedSlot] );

lastSelected = selectedSlot;

break;

}

}

}

yield return permutation;

#region Update offsets

for ( int i = 0; i < numElements; i++ ) {

slotOffsets[i]++;

if ( slotOffsets[i] < ( numElements - i ) ) {

break;

}

else {

if ( i == numElements - 1 ) {

allDone = true;

}

else {

slotOffsets[i] = 0;

}

}

}

#endregion

}

}

}

...which you can use as follows (notice how it's magically a method on any IList<> implementation?):

IList<int> inputList = new List<int> ( new int[] { 1, 2, 3 } );

foreach ( List<int> permutation in inputList.Permutations ( ) ) {

StringBuilder sb = new StringBuilder ( );

sb.Append ( "[" );

bool isFirst = true;

foreach ( var item in permutation ) {

if ( !isFirst ) {

sb.Append ( ", " );

}

else {

isFirst = false;

}

sb.Append ( item );

}

sb.Append ( "]" );

Console.WriteLine ( sb.ToString() );

}

...and it should produce the following output:

[1, 2, 3]

[2, 3, 1]

[3, 1, 2]

[1, 3, 2]

[2, 1, 3]

[3, 2, 1]

I just wish I had prepared this method

*before*the contest, although I think some actual practice in solving these kinds of problems would have helped me more. Maybe next time... :)

## No comments:

Post a Comment