Permutation

SRM 160 · 2003-08-23 · by dgoodman

SRM 160 · 2003-08-23 · by dgoodman · Graph Theory, Math, String Manipulation

Show categories

Class Name: Permutation

Return Type: String

Method Name: best

Arg Types: (int)

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).

Constraints

n is between 1 and 52 inclusive

Examples

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

7
Returns: "BCAEFGD"

This is the lexicographically first permutation with cycle length 12

29
Returns: "BCDEAGHIJKLFNOPQRSTMVWXYZabcU"

1
Returns: "A"

8
Returns: "BCAEFGHD"

Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Permutation with a public method string best(int n) · 53 test cases · 2 s / 256 MB per case