java - 字符串的有序固定长度组合

Question

我需要编写一个函数来查找字符串的可能固定长度组合。需要的是并非所有组合都是必需的。例如，如果字符串是“abcde”，我们需要长度为 3 的组合，那么函数必须返回以下内容：

abc
abd
abe
acd
ace
ade
bcd
bde
bce
cde

没有别的。我一直在尝试使用递归，但事情并没有按预期进行。我也看到了一些类似的问题，但无法从中得到太多。算法或代码（C、C++、Java），欢迎任何帮助。谢谢。！

注意：需要订购组合。也就是说，字符应遵循与输入字符串中相同的顺序。

Answer 1

在有三个输入的情况下，您有三个索引，最初设置为输入字符串的前三个索引。打印出来，然后将最后一个索引加一，然后打印出所有索引。继续直到到达输入字符串的末尾，然后增加第二个索引并在第二个之后将第三个重置为下一个。继续直到第二个索引是倒数第二个字符，然后增加第一个索引，并将第二个和第三个连续放置在第一个之后。继续...

让我试着说明一下：

输入：[abcde]
         ^^^
         123

输出：abc

下一次迭代：

输入：[abcde]
         ^^ ^
         12 3

输出：abd

下一次迭代：

输入：[abcde]
         ^^ ^
         12 3

输出：阿贝

下一次迭代：

输入：[abcde]
         ^^^
         1 23

输出：acd

下一次迭代：

输入：[abcde]
         ^ ^ ^
         1 2 3

输出：王牌

下一次迭代：

输入：[abcde]
          ^^^
          123

输出：bcd

下一次迭代：

输入：[abcde]
          ^^ ^
          12 3

输出：公元前

下一次迭代：

输入：[abcde]
          ^^^
          1 23

输出：bde

下一次迭代：

输入：[abcde]
           ^^^
           123

输出：cde

Answer 2

1. 由于您的要求是 3 的特定长度，因此将您分成String3 块，然后应用算法。

2. 从你的 3 个字符中取出一个字符String，并计算剩余 2 个字符的可能排列。

3. 将该字符放在计算排列的所有可能位置上。

4. 重复上面。

Answer 3

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>


int main()
{
    char buf[6] = "abcde";
    int len = strlen(buf);
   // std::vector<std::string> char_list;
    for(int i = 0; i < len; ++i){
        for(int j = i+1; j < len;++j){
                //if (i==j)continue;
                for(int k = j+1; k < len;++k){
                        //if(i == k || j == k)
                        //      continue;
                        char temp[4]="";
                        temp[0] = buf[i];
                        temp[1] = buf[j];
                        temp[2] = buf[k];
                        temp[3] = '\0';
                        std::cout << temp << std::endl;
                        //show(temp,3);
                        //char_list.push_back(key);
                }
        }
    }

    return 0;
}

Answer 4

我希望可以做得更好，但这是我可以很快想到的。

我用 aList来保持秩序，不得不尴尬地避免重复。使用 aSet可以让我们跳过result.contains(s)检查，但更好的算法可能会以更简洁的方式避免重复。

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