public class StringPermutation {
public static List<String> getPermutation(String input) {
List<String> collection = null;
if (input.length() == 1) {
collection = new ArrayList<String>();
collection.add(input);
return collection;
} else {
collection = getPermutation(input.substring(1));
Character first = input.charAt(0);
List<String> result = new ArrayList<String>();
for (String str : collection) {
for (int i = 0; i < str.length(); i++) {
String item = str.substring(0, i) + first
+ str.substring(i);
result.add(item);
}
String item = str.concat(first.toString());
result.add(item);
}
return result;
}
}
public static void main(String[] args) {
List<String> test = StringPermutation.getPermutation ("CAT");
System.out.println (test);
}
}
上面的代码对给定的字符串进行排列。例如,给定cat
,它返回[cat, act, atc, cta, tca, tac
],这非常好,但是你们可以编辑我的代码,以便它也显示字母的子集,即[cat, act, atc, cta, tca, tac]和[at, ta, tc, ca, ac, ct, c, a, t
]?
最佳答案
我认为您可以首先生成字母的所有子集,然后生成给定子集的所有排列:
Set<String> subsets;
public void generateSubsets(String current, String left) {
if (left.length() == 0) {
subsets.add(current);
} else {
generateSubsets(current, left.substring(1));
generateSubsets(current + left.charAt(0), left.substring(1));
}
}
List<String> allPermutations(String word) {
subsets = new HashSet<String>();
generateSubsets("", word);
List<String> result = new ArrayList<String>();
for (String subset : subsets) {
result.addAll(StringPermutation.getPermutation(subset));
}
return result;
}
如果你有“猫”
子集为:“”、“c”、“a”、“t”、“ca”、“ct”、“tc”、“cat”
然后你就可以得到每个子集的排列。
就效率而言,这不是最好的解决方案,但你可以改进它。
关于java - 将每个组合排列为字母,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10130909/