So I've been working on this problem today in Java. I feel like I'm coming close to possibly having AC, but I've run into an issue of not being able to sort the list of permutations of a string that I have in such a way that A > a > B > b > C > ...
Has anyone been in this sort of situation before? Could I avoid this situation altogether by taking a separate route in solving this problem. Below is my code. Thanks for reading.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.io.IOException;
import java.util.HashMap;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.util.Comparator;
import java.util.Collections;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author Miles Stevenson
*/
public class Main
{
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task195 solver = new Task195();
solver.solve(1, in, out);
out.close();
}
static class Task195
{
Map<Character, Integer> orderMap = new HashMap<>();
public void solve(int testNumber, InputReader in, PrintWriter out) {
generateOrder();
int n = in.nextInt();
for (int i = 0; i < n; i++) {
char[] word = in.nextLine().toCharArray();
List<Character> wordList = convertToLexiList(word);
Set<String> perms = permutations(wordList);
for (String s : perms) {
out.println(s);
}
}
}
private List<Character> convertToLexiList(char[] word) {
List<Character> list = new ArrayList<>();
for (int i = 0; i < word.length; i++) {
list.add(new Character(word[i]));
}
Collections.sort(list, new LexiComparator());
return list;
}
private void generateOrder() {
orderMap.put('A', 0);
orderMap.put('a', 1);
orderMap.put('B', 2);
orderMap.put('b', 3);
orderMap.put('C', 4);
orderMap.put('c', 5);
orderMap.put('D', 6);
orderMap.put('d', 7);
orderMap.put('E', 8);
orderMap.put('e', 9);
orderMap.put('F', 10);
orderMap.put('f', 11);
orderMap.put('G', 12);
orderMap.put('g', 13);
orderMap.put('H', 14);
orderMap.put('h', 15);
orderMap.put('I', 16);
orderMap.put('i', 17);
orderMap.put('J', 18);
orderMap.put('j', 19);
orderMap.put('K', 20);
orderMap.put('k', 21);
orderMap.put('L', 22);
orderMap.put('l', 23);
orderMap.put('M', 24);
orderMap.put('m', 25);
orderMap.put('N', 26);
orderMap.put('n', 27);
orderMap.put('O', 28);
orderMap.put('o', 29);
orderMap.put('P', 30);
orderMap.put('p', 31);
orderMap.put('Q', 32);
orderMap.put('q', 33);
orderMap.put('R', 34);
orderMap.put('r', 35);
orderMap.put('S', 36);
orderMap.put('s', 37);
orderMap.put('T', 38);
orderMap.put('t', 39);
orderMap.put('U', 40);
orderMap.put('u', 41);
orderMap.put('V', 42);
orderMap.put('v', 43);
orderMap.put('W', 44);
orderMap.put('w', 45);
orderMap.put('X', 46);
orderMap.put('x', 47);
orderMap.put('Y', 48);
orderMap.put('y', 49);
orderMap.put('Z', 50);
orderMap.put('z', 51);
}
Set<String> permutations(List<Character> word) {
Set<String> perm = new TreeSet<>();
if (word.size() == 1) {
perm.add(String.valueOf(word.get(0)));
return perm;
}
for (int i = 0; i < word.size(); i++) {
String rem = Character.toString(word.get(i));
List<Character> altered_word = new ArrayList(word);
altered_word.remove(i);
Set<String> k_perm = permutations(altered_word);
for (String s : k_perm) {
s = rem.concat(s);
perm.add(s);
}
}
return perm;
}
class LexiComparator implements Comparator<Character>
{
public int compare(Character first, Character second) {
return orderMap.get(first).compareTo(orderMap.get(second));
}
}
}
static class InputReader
{
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String nextLine() {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
public String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(nextLine());
}
return tokenizer.nextToken();
} catch (NullPointerException e) {
return null;
}
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}