1 
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]？

我希望你明白我在问什么。如果您不明白，请告诉我，我会进一步解释。谢谢，我很感激。

4

1 回答 1

1

我认为您可以首先生成所有字母子集，然后为给定子集生成所有排列：

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;
}

所以如果你有“cat”子集将是：“”、“c”、“a”、“t”、“ca”、“ct”、“tc”、“cat”然后你会得到每个子集的排列。
关于效率，它不是最好的解决方案，但您可以改进它。

于 2012-04-12T20:48:12.867 回答