如何在Java中打印0,1,2的字典排序排列
如何在Java中打印0,1,2的字典排序排列
如何打印给定整数值的词典排列。例如,如果我给定012,输出应为012 021 102 120 201 210。
我尝试了以下方法来实现这个目标,
package TestingHere; public class LexicographicPermutations { private static int permutationsFound = 0; public static void main(String[] args) { permuteTo("012", ""); } private static void permuteTo(String s, String chosen) { if (s.length() == 0) { permutationsFound++; if (permutationsFound == 1000000) { System.out.println(chosen); } } else if (permutationsFound <= 1000000) { for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); String rest = s.substring(0, i) + s.substring(i + 1); // System.out.println(rest); permuteTo(rest, chosen + ch); } System.out.println(chosen); } } }
但是这段代码不能满足我的要求。
请问有人可以告诉我如何做到这一点吗?
在Java中打印0、1、2的字典序排列的问题出现的原因是为了按照字典序打印给定数字的排列。下面给出了解决这个问题的方法。
根据维基百科的算法,可以实现以下算法来打印数字的字典序排列。该算法会原地修改给定的排列。
1. 找到最大的索引k,使得a[k] < a[k + 1]。如果不存在这样的索引,那么这个排列就是最后一个排列。
2. 找到大于k的最大索引l,使得a[k] < a[l]。
3. 交换a[k]和a[l]的值。
4. 反转从a[k + 1]到最后一个元素a[n]的顺序。
以下是用Java代码实现这个算法的例子:
public class LexicographicPermutations { public static void main(String[] args) { int[] nums = {0, 1, 2}; printPermutations(nums); } public static void printPermutations(int[] nums) { while (true) { // 打印当前排列 for (int num : nums) { System.out.print(num + " "); } System.out.println(); // 找到最大的k int k = -1; for (int i = 0; i < nums.length - 1; i++) { if (nums[i] < nums[i + 1]) { k = i; } } // 如果不存在k,说明已经是最后一个排列 if (k == -1) { break; } // 找到大于k的最大的l int l = -1; for (int i = k + 1; i < nums.length; i++) { if (nums[k] < nums[i]) { l = i; } } // 交换a[k]和a[l]的值 int temp = nums[k]; nums[k] = nums[l]; nums[l] = temp; // 反转从a[k + 1]到最后一个元素的顺序 int start = k + 1; int end = nums.length - 1; while (start < end) { temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } } } }
这样就可以按照字典序打印出0、1、2的所有排列。
希望这篇文章对你有帮助!
问题:如何在Java中打印0、1、2的字典序排列?
原因:该问题的出现可能是因为需要对给定的数字进行字典序排列,并将结果打印出来。
解决方法:可以使用递归方法来实现字典序排列,并将结果存储在List中。具体步骤如下:
1. 创建一个LexicographicPermutations类,其中包含一个私有的baseString变量和一个permutations列表,用于存储排列结果。
2. 在LexicographicPermutations类中,创建一个构造函数,接受一个baseString参数,并将其赋值给baseString变量。
3. 在LexicographicPermutations类中,创建一个公有的getPermutations方法,用于获取排列结果。在该方法中,调用私有的递归方法recursePermutations,并返回permutations列表。
4. 在LexicographicPermutations类中,创建一个私有的递归方法recursePermutations,该方法接受两个参数:递归次数和当前结果字符串。
5. 在recursePermutations方法中,首先判断递归次数是否为0。如果是,表示已经生成了一个完整的排列结果。接下来,判断结果字符串是否已经存在于permutations列表中,如果存在,则直接返回。然后,遍历baseString中的每个字符,查找结果字符串中是否包含该字符,如果包含,则从结果字符串中删除该字符。最后,判断结果字符串的长度是否为0,如果是,则将结果字符串添加到permutations列表中。
6. 如果递归次数不为0,则遍历baseString中的每个字符,并调用recursePermutations方法进行递归,并将递归次数减1,结果字符串添加上当前字符。
7. 在Main类的main方法中,创建一个LexicographicPermutations对象,并调用getPermutations方法获取排列结果。然后,使用for循环遍历排列结果,并打印每个结果字符串。
完整代码如下:
import java.util.List; import java.util.ArrayList; public class Main { public class LexicographicPermutations { private final String baseString; private final Listpermutations = new ArrayList (); public LexicographicPermutations(String baseString) { this.baseString = baseString; } public List getPermutations() { recursePermutations(baseString.length(), ""); return permutations; } private void recursePermutations(int recursionsLeft, String result) { if (recursionsLeft == 0) { if (permutations.contains(result)) { return; } int total = 0; StringBuilder resultTemp = new StringBuilder(result); for (int current = 0; current < baseString.length(); current++) { int position = resultTemp.indexOf(String.valueOf(baseString.charAt(current))); if (position >= 0) { resultTemp.deleteCharAt(position); } } if (resultTemp.length() == 0) { permutations.add(result); } return; } for (int index = 0; index < baseString.length(); index++) { recursePermutations(recursionsLeft - 1, result + baseString.charAt(index)); } } } public static void main(String[] args) { for (String permutation : new Main().new LexicographicPermutations("012").getPermutations()) { System.out.println(permutation); } } }
以上代码可以实现对0、1、2的字典序排列的打印输出。
问题的出现原因是代码中使用了Map的replace方法,但是该方法在该版本的Java中不存在。解决方法是修改代码,使其支持之前的Java版本。以下是修改后的代码:
import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class LexicographicPermutations { public static void main(String[] args) { System.out.println(permute("3211")); } private static String permute(String inputString) { // for permutations we must disregard equal final MapinputAlphabet = new HashMap (); final Map disregard = new HashMap (); final StringBuilder output = new StringBuilder(); final char[] inputAsCharArray = inputString.toCharArray(); Arrays.sort(inputAsCharArray); for (final char c : inputAsCharArray) { if (inputAlphabet.containsKey("" + c)) { inputAlphabet.put("" + c, inputAlphabet.get("" + c) + 1); } else { inputAlphabet.put("" + c, 1); } } permute(inputAlphabet, disregard, " ", inputString.length(), output); return output.toString(); } private static String permute(Map inputAlphabet, Map disregard, String start, int length, StringBuilder output) { final StringBuilder sb = new StringBuilder(); for (final String s : inputAlphabet.keySet()) { for (int i = 0; i < (inputAlphabet.get(s) - (disregard.containsKey(s) ? disregard.get(s) : 0)); i++) { if (disregard.containsKey(s)) { disregard.put(s, disregard.get(s) + i + 1); } else { disregard.put(s, i + 1); } sb.append(permute(inputAlphabet, disregard, start + s, length - 1, output)); if ((disregard.get(s) - i - 1) != 0) { disregard.put(s, disregard.get(s) - i - 1); } else { disregard.remove(s); } } } if (sb.length() == length) { output.append(start + sb.toString()); return start + sb.toString(); } else { return start + sb.toString(); } } }
这样修改后的代码可以在之前的Java版本中正常运行。