Permutation ----------- Given two equal length strings of upper case letters, find a permutation that maps the first string to the second string. Input ----- For each of several test cases, first a line that gives the test case name, and then two lines each containing one of the two strings. All lines are at most 80 char- acters long. Input ends with an end of file. Output ------ For each test case, first an exact copy of the test case name line. Then N lines where N is the common length of the input strings. Each of the N lines has the form: L: I -> J where L is a letter that is in position I in the first string and position J in the second string. Positions are numbered 1, 2, ..., N. Each position must appear EXACTLY ONCE as I on the N lines, and also exactly once as J in the N lines, so that the N lines define a permutation (i.e., a 1-1 map). If this is not possible, output a single line contain- ing just the word `impossible' in lower case letters, in place of the N lines. For example, if the input is: ABC ABA the output: A: 1 -> 1 B: 2 -> 2 A: 1 -> 3 is incorrect because 3 does not appear as I in any of the 3 lines, and also because 1 appears as I more than once. In fact, as the second string has more A's than the first string, there are no permutations that map the first string to the second string, and the correct answer is `impossible'. There may be more than one correct solution. If so, give only one solution. Sample Input ------ ----- -- SAMPLE 1 -- ABC CBA -- SAMPLE 2 -- ABC ABA -- SAMPLE 3 -- ABCDEFG GFEDCBA -- SAMPLE 4 -- ABABAB BBBAAA -- SAMPLE 5 -- ABABAB BBBAAC [see sample.in for more sample input] Sample Output ------ ------ -- SAMPLE 1 -- A: 1 -> 3 B: 2 -> 2 C: 3 -> 1 -- SAMPLE 2 -- impossible -- SAMPLE 3 -- A: 1 -> 7 B: 2 -> 6 C: 3 -> 5 D: 4 -> 4 E: 5 -> 3 F: 6 -> 2 G: 7 -> 1 -- SAMPLE 4 -- A: 1 -> 4 B: 2 -> 1 A: 3 -> 5 B: 4 -> 2 A: 5 -> 6 B: 6 -> 3 -- SAMPLE 5 -- impossible [see sample.test for more sample output] File: permutation.txt Author: Shai Simonson Editor: Bob Walton Date: Fri Oct 5 21:35:32 EDT 2018 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.