TopCoder problem "Permutation" used in SRM 160 (Division I Level Three)



Problem Statement

    A permutation of the letters in an alphabet can be described by a string that contains each letter exactly once. For example, CABD describes the permutation of ABCD that maps A to C, B to A, C to B, and D to D. If we repeatedly apply that permutation, we will get the sequence ABCD,CABD,BCAD,ABCD,CABD,BCAD,ABCD,... This permutation is cyclic with length 3.

We want to find the permutation of the first n letters of

    ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
that has the longest cycle. Create a class Permutation that contains the method best that takes the number of characters n as input and returns the lexicographically first permutation that has the maximum possible cycle length.

"Lexicographically first" means the String that would sort first among all the permutations of maximum cycle length, using the ASCII sequence (which sorts uppercase letters before lowercase letters).

 

Definition

    
Class:Permutation
Method:best
Parameters:int
Returns:String
Method signature:String best(int n)
(be sure your method is public)
    
 

Constraints

-n is between 1 and 52 inclusive
 

Examples

0)
    
6
Returns: "ACBEFD"
This permutation has cycle length 6. So does BDEFCA, but ACBEFD is lexicographically first. The cycle is: ABCDEF -> ACBEFD -> ABCFDE -> ACBDEF -> ABCEFD -> ACBFDE -> ABCDEF
1)
    
7
Returns: "BCAEFGD"
This is the lexicographically first permutation with cycle length 12
2)
    
29
Returns: "BCDEAGHIJKLFNOPQRSTMVWXYZabcU"
3)
    
1
Returns: "A"
4)
    
8
Returns: "BCAEFGHD"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1135

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4605&pm=1135

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Graph Theory, Math, String Manipulation