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] and [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"然后你会得到每个子集的排列。
关于效率,这不是最好的解决方案,但您可以改进它。