fork download
copy 
  1. import java.io.OutputStream;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.PrintWriter;
  5. import java.util.Set;
  6. import java.io.IOException;
  7. import java.util.HashMap;
  8. import java.io.InputStreamReader;
  9. import java.util.TreeSet;
  10. import java.util.ArrayList;
  11. import java.util.List;
  12. import java.util.StringTokenizer;
  13. import java.util.Map;
  14. import java.io.BufferedReader;
  15. import java.util.Comparator;
  16. import java.util.Collections;
  17. import java.io.InputStream;
  18.  
  19. /**
  20.  * Built using CHelper plug-in
  21.  * Actual solution is at the top
  22.  *
  23.  * @author
  24.  */
  25. public class Main
  26. {
  27. 	public static void main(String[] args) {
  28. 		InputStream inputStream = System.in;
  29. 		OutputStream outputStream = System.out;
  30. 		InputReader in = new InputReader(inputStream);
  31. 		PrintWriter out = new PrintWriter(outputStream);
  32. 		Task195 solver = new Task195();
  33. 		solver.solve(1, in, out);
  34. 		out.close();
  35. 	}
  36.  
  37. 	static class Task195
  38. 	{
  39. 		Map<Character, Integer> orderMap = new HashMap<>();
  40.  
  41. 		public void solve(int testNumber, InputReader in, PrintWriter out) {
  42. 			generateOrder();
  43. 			int n = in.nextInt();
  44. 			for (int i = 0; i < n; i++) {
  45. 				char[] word = in.nextLine().toCharArray();
  46. 				List<Character> wordList = convertToLexiList(word);
  47. 				Set<String> perms = permutations(wordList);
  48. 				for (String s : perms) {
  49. 					out.println(s);
  50. 				}
  51. 			}
  52. 		}
  53.  
  54. 		private List<Character> convertToLexiList(char[] word) {
  55. 			List<Character> list = new ArrayList<>();
  56. 			for (int i = 0; i < word.length; i++) {
  57. 				list.add(new Character(word[i]));
  58. 			}
  59. 			Collections.sort(list, new LexiComparator());
  60. 			return list;
  61. 		}
  62.  
  63. 		private void generateOrder() {
  64. 			orderMap.put('A', 0);
  65. 			orderMap.put('a', 1);
  66. 			orderMap.put('B', 2);
  67. 			orderMap.put('b', 3);
  68. 			orderMap.put('C', 4);
  69. 			orderMap.put('c', 5);
  70. 			orderMap.put('D', 6);
  71. 			orderMap.put('d', 7);
  72. 			orderMap.put('E', 8);
  73. 			orderMap.put('e', 9);
  74. 			orderMap.put('F', 10);
  75. 			orderMap.put('f', 11);
  76. 			orderMap.put('G', 12);
  77. 			orderMap.put('g', 13);
  78. 			orderMap.put('H', 14);
  79. 			orderMap.put('h', 15);
  80. 			orderMap.put('I', 16);
  81. 			orderMap.put('i', 17);
  82. 			orderMap.put('J', 18);
  83. 			orderMap.put('j', 19);
  84. 			orderMap.put('K', 20);
  85. 			orderMap.put('k', 21);
  86. 			orderMap.put('L', 22);
  87. 			orderMap.put('l', 23);
  88. 			orderMap.put('M', 24);
  89. 			orderMap.put('m', 25);
  90. 			orderMap.put('N', 26);
  91. 			orderMap.put('n', 27);
  92. 			orderMap.put('O', 28);
  93. 			orderMap.put('o', 29);
  94. 			orderMap.put('P', 30);
  95. 			orderMap.put('p', 31);
  96. 			orderMap.put('Q', 32);
  97. 			orderMap.put('q', 33);
  98. 			orderMap.put('R', 34);
  99. 			orderMap.put('r', 35);
  100. 			orderMap.put('S', 36);
  101. 			orderMap.put('s', 37);
  102. 			orderMap.put('T', 38);
  103. 			orderMap.put('t', 39);
  104. 			orderMap.put('U', 40);
  105. 			orderMap.put('u', 41);
  106. 			orderMap.put('V', 42);
  107. 			orderMap.put('v', 43);
  108. 			orderMap.put('W', 44);
  109. 			orderMap.put('w', 45);
  110. 			orderMap.put('X', 46);
  111. 			orderMap.put('x', 47);
  112. 			orderMap.put('Y', 48);
  113. 			orderMap.put('y', 49);
  114. 			orderMap.put('Z', 50);
  115. 			orderMap.put('z', 51);
  116. 		}
  117.  
  118. 		Set<String> permutations(List<Character> word) {
  119. 			Set<String> perm = new TreeSet<>(new LexiStringComparator());
  120. 			if (word.size() == 1) {
  121. 				perm.add(String.valueOf(word.get(0)));
  122. 				return perm;
  123. 			}
  124.  
  125. 			for (int i = 0; i < word.size(); i++) {
  126. 				String rem = Character.toString(word.get(i));
  127. 				List<Character> altered_word = new ArrayList(word);
  128. 				altered_word.remove(i);
  129. 				Set<String> k_perm = permutations(altered_word);
  130. 				for (String s : k_perm) {
  131. 					s = rem.concat(s);
  132. 					perm.add(s);
  133. 				}
  134. 			}
  135. 			return perm;
  136. 		}
  137.  
  138. 		class LexiComparator implements Comparator<Character>
  139. 		{
  140.  
  141. 			public int compare(Character first, Character second) {
  142. 				return orderMap.get(first).compareTo(orderMap.get(second));
  143. 			}
  144.  
  145. 		}
  146.  
  147. 		class LexiStringComparator implements Comparator<String>
  148. 		{
  149.  
  150. 			public int compare(String first, String second) {
  151. 				LexiComparator cmp = new LexiComparator();
  152. 				int result = 0;
  153. 				for (int i = 0; i < first.length(); i++) {
  154. 					result = cmp.compare(first.charAt(i), second.charAt(i));
  155. 					if (result != 0) {
  156. 						return result;
  157. 					}
  158. 				}
  159. 				return 0;
  160. 			}
  161.  
  162. 		}
  163.  
  164. 	}
  165.  
  166. 	static class InputReader
  167. 	{
  168. 		private BufferedReader reader;
  169. 		private StringTokenizer tokenizer;
  170.  
  171. 		public InputReader(InputStream stream) {
  172. 			reader = new BufferedReader(new InputStreamReader(stream));
  173. 			tokenizer = null;
  174. 		}
  175.  
  176. 		public String nextLine() {
  177. 			try {
  178. 				return reader.readLine();
  179. 			} catch (IOException e) {
  180. 				throw new RuntimeException(e);
  181. 			}
  182. 		}
  183.  
  184. 		public String next() {
  185. 			try {
  186. 				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  187. 					tokenizer = new StringTokenizer(nextLine());
  188. 				}
  189. 				return tokenizer.nextToken();
  190. 			} catch (NullPointerException e) {
  191. 				return null;
  192. 			}
  193. 		}
  194.  
  195. 		public int nextInt() {
  196. 			return Integer.parseInt(next());
  197. 		}
  198.  
  199. 	}
  200. }
  201.  
  202.  
Success #stdin #stdout 0.11s 320512KB
comments (?)
stdin
copy 
3
aAb
abc
acba
stdout
copy 
Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
https://ideone.com/dlBb0H
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!