Lexicographic Permutations

22Dec13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

Lexicographic Permutations

For the purposes of this problem the characters of the string “Contest Coding” are assigned values, the value assigned to a particular character determined by the position in the string of that character – viz:

‘C’ (1), ‘o’ (2), ‘n’ (3), …etc.…, ‘i’ (12), ‘n’ (13), ‘g’ (14)

That sequence of values is considered the 1st lexicographic permutation; given the characters to which those values are assigned, what nth lexicographic permutation will first contain the sequence of characters “tsetnoC”?

– This puzzle was suggested by Mark Bishop

Exemplar solution and answer (LexicographicPermutations.java):

/*
Exemplar solution and answer for potential problem "Lexicographic Permutations" of http://ContestCoding.WordPress.com/

Sun Dec 22 09:00:00 GMT+00:00 2013

366745 ("ContsetnoC dig")

Sun Dec 22 09:36:09 GMT+00:00 2013

Solution programmed in Java using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition); solution took ~36m to run on a 80MHz PowerPC 601.
*/

import java.util.Date;

public class LexicographicPermutations
{
  private static boolean generatePermutation( int p[] )
  {
    int k = p.length - 2;
    boolean k_found = false;
    for( ; k >= 0; k -- )
      if( p[ k ] < p[ k + 1 ] )
      {
        k_found = true;
        break;
      }
    if( !k_found )
      return false;
    int l = p.length - 1;
    for( ; l > k; l -- )
      if( p[ l ] > p[ k ] )
        break;
    final int v = p[ k ];
    p[ k ] = p[ l ];
    p[ l ] = v;
    reverse( p, k + 1 );
    return true;
  }

  private static void reverse( int p_a[], int p_i )
  {
    int k = p_a.length - 1;
    while( p_i < k )
    {
      final int v = p_a[ p_i ];
      p_a[ p_i ] = p_a[ k ];
      p_a[ k ] = v;
      p_i ++;
      k --;
    }
  }

  private static boolean arrayContainsSubstring( int p_a[], String p_substring )
  {
    return arrayToString( p_a ).indexOf( p_substring ) != -1;
  }

  private static final String STRING = "Contest Coding";

  private static String arrayToString( int p[] )
  {
    String s = "";
    for( int i = 0; i < p.length; i ++ )
      s += STRING.charAt( p[ i ] - 1 );
    return s;
  }

  public static void main( String p[] )
  {
    System.out.println( new Date());

    int a[] = new int[ STRING.length() ];
    long i = 0;
    for( ; i < a.length; i ++ )
      a[ ( int )i ] = ( int )i + 1;
    i = 1;
    while( !arrayContainsSubstring( a, "tsetnoC" ))
    {
      generatePermutation( a );
      i ++;
    }
    System.out.println( "\n" + i + " (\"" + arrayToString( a ) + "\")\n" );

    System.out.println( new Date());
  }
}
Advertisements


No Responses Yet to “Lexicographic Permutations”

  1. Leave a Comment

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


%d bloggers like this: