一个字符串的有序固定长度的组合 [英] Ordered Fixed Length Combinations of a String

问题描述

我需要写一个找到字符串的可能的固定长度的组合的功能。需要的是，不是所有的combis都是必需的。例如，如果字符串为ABCDE，我们需要一个长度为3 combis，则函数必须返回以下内容：

I need to write a function which finds the possible fixed length combinations of a string. The need is that not all combis are required. For example, if the string is "abcde", and we need combis of length 3, then the function must return the following:

abc
abd
abe
acd
ace
ade
bcd
bde
bce
cde

再没有别的。我一直在试图为它使用递归，但如预期的东西还没有制定。我也看到了一些类似的问题，但不能获得太多了出来。算法或code（C，C ++，Java的），任何帮助是值得欢迎的。谢谢！

and none else. I have been trying for it using recursion but things have not worked out as expected. I have also seen some similar questions but could not get much out of them. Algorithm or code(C, C++, Java), any help is welcome. Thanks.!

注：组合需要订购。即，字符应遵循相同的顺序输入字符串

Note: The combinations need to be ordered. That is, the characters should follow the same order as in the input string.

推荐答案

我希望它可能做的更好，但是这是我能想出快。

I expect it's possible to do better, but this is what I could come up with quickly.

我用了一个列表来preserve秩序，不得不以避免重复笨拙。使用设置，而不是使我们能够跳过 result.contains（S）检查，但更好的算法，可避免重复的以清洁的方式。

I used a List to preserve order, and had to avoid duplicates awkwardly. Using a Set instead would allow us to skip the result.contains(s) check, but a better algorithm might avoid the duplicates in a cleaner way.

private static List<String> substrings(int i, String input) {
    List<String> result = new ArrayList<String>();
    if (i == 0)
        return result;

    String first = input.substring(0, i);
    result.add(first);

    if (input.length() == i) {
        return result;
    }

    // Recursively find substrings of next smaller length not including the first character
    List<String> tails = substrings(i-1, input.substring(1));

    // Append first char to each result of the recursive call.
    for (String sub: tails) {
        String s = input.substring(0, 1) + sub;
        if (!(result.contains(s)))
            result.add(s);
    }

    // Add all substring of current length not including first character
    result.addAll(substrings(i, input.substring(1)));
    return result;
}

这篇关于一个字符串的有序固定长度的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！