找到给定字符串的每个可能的子集

Question

我试图在 Java 中找到每个可能的字符串变位词 - 我的意思是，如果我有一个 4 个字符长的单词，我想要从它派生的所有可能的 3 个字符长的单词，所有 2 个字符长和所有 1 个字符长。我想到的最直接的方法是在字符串上使用两个嵌套的 for 循环和 iterare。这是我现在的代码：

private ArrayList<String> subsets(String word){
        ArrayList<String> s = new ArrayList<String>();
        int length = word.length();
        for (int c=0; c<length; c++){
            for (int i=0; i<length-c; i++){
                String sub = word.substring(c, c+i+1);
                System.out.println(sub);
                //if (!s.contains(sub) && sub!=null) 
                    s.add(sub);
            }
        }
        //java.util.Collections.sort(s, new MyComparator());
        //System.out.println(s.toString());
        return s;
    }

我的问题是它适用于 3 个字母的单词，fun 产生了这个结果（不要介意顺序，单词经过处理，所以我有一个按字母顺序排列的字符串）：

f
fn
fnu
n
nu
u

但是当我尝试 4 个字母的单词时，它遗漏了一些东西，如 catq 中给我的：

a
ac
acq
acqt
c
cq
cqt
q
qt
t

即，我没有看到 3 个字符的长词 act - 这是我在测试此方法时要寻找的词。我不明白问题出在哪里，这很可能是我在创建子字符串时犯的逻辑错误。如果有人可以帮助我，请不要给我代码，而是给我解决方案背后的原因。这是一个课程作业，我需要自己想出代码。

编辑：清除一些东西，对我来说 acq、qca、caq、aqc、cqa、qac 等都是一样的——为了让它更清楚，什么发生的是字符串按字母顺序排序，所以所有这些排列应该作为一个唯一的结果出现，acq。所以，我不需要字符串的所有排列，而是给定一个 4 个字符长的字符串，我可以从中导出所有 3 个字符长的字符串 - 这意味着一次取出一个字符并返回该字符串结果，对原始字符串中的每个字符都这样做。我希望我的问题更清楚了

Answer 1

它工作正常，您只是在 tests/input 中将 "caqt" 拼错为 "acqt"。

（问题可能是您正在对输入进行排序。如果您想要 substrings，则必须不对输入进行排序。）

编辑后：查看 Generating all permutations of a given string 然后只需对单个字母进行排序，然后将它们放在一个集合中。

Answer 2

这是我想出的方法，好像行得通

private void subsets(String word, ArrayList<String> subset){
        if(word.length() == 1){
            subset.add(word);
            return;
        } 
        else {
            String firstChar = word.substring(0,1);
            word = word.substring(1);
            subsets(word, subset);
            int size = subset.size();
            for (int i = 0; i < size; i++){
                String temp = firstChar + subset.get(i);
                subset.add(temp);
            }
            subset.add(firstChar);
            return;
        }
    }

我所做的是检查单词是否大于一个字符，否则我将单独将该字符添加到 ArrayList 并开始递归过程。如果它更大，我保存第一个字符并用字符串的其余部分进行递归调用。发生的事情是整个字符串被切成递归堆栈中保存的字符，直到我到达我的单词长度为 1 的点，只剩下一个字符。

发生这种情况时，正如我在开始时所说，字符被添加到列表中，现在递归开始并查看数组的大小，在第一次迭代中是 1，然后用 for loop 添加保存在堆栈中的字符，用于与 ArrayList 中的每个元素连接的先前调用。然后它自己添加字符并再次展开递归。即，使用 fun 这个词会发生这种情况：

f saved
List empty
recursive call(un)
-
u saved
List empty
recursive call(n)
-
n.length == 1
List = [n]
return
-
list.size=1
temp = u + list[0]
List = [n, un]
add the character saved in the stack on its own
List = [n, un, u]
return
-
list.size=3
temp = f + list[0]
List = [n, un, u, fn]
temp = f + list[1]
List = [n, un, u, fn, fun]
temp = f + list[2]
List = [n, un, u, fn, fun, fu]
add the character saved in the stack on its own
List = [n, un, u, fn, fun, fu, f]
return

我已经尽可能清楚了，我希望这能澄清我最初的问题是什么以及如何解决它。

Answer 3

这是工作代码：

public static void main(String[] args) {
    String input = "abcde";
    Set<String> returnList = permutations(input);
    System.out.println(returnList);
}

private static Set<String> permutations(String input) {
    if (input.length() == 1) {
        Set<String> a = new TreeSet<>();
        a.add(input);
        return a;
    }
    Set<String> returnSet = new TreeSet<>();

    for (int i = 0; i < input.length(); i++) {
        String prefix = input.substring(i, i + 1);
        Set<String> permutations = permutations(input.substring(i + 1));
        returnSet.add(prefix);
        returnSet.addAll(permutations);
        Iterator<String> it = permutations.iterator();
        while (it.hasNext()) {
            returnSet.add(prefix + it.next());
        }
    }
    return returnSet;
}

Answer 4

好的，既然你已经设计了自己的解决方案，我会告诉你我的看法。首先，考虑您的结果列表有多大。您实际上是在轮流获取每个字母，包括或不包括它。每个字母有 2 种可能性，总共有 2^n 个结果，其中 n 是字母数。这当然包括您不使用任何字母并以空字符串结尾的情况。

接下来，如果您用 0 表示 'include this letter'，用 1 表示不包括它，以您的 'fnu' 为例，您最终会得到：

000 - ''
001 - 'u'
010 - 'n'
011 - 'nu'
100 - 'f'
101 - 'fu' (no offense intended)
110 - 'fn'
111 - 'fnu'.

显然，这些只是二进制数，你可以推导出一个函数，给定 0-7 中的任意数字和三个字母输入，将计算相应的子集。

在 java 中很容易做到。手头没有 java 编译器，但这应该是大致正确的：

public string getSubSet(string input, int index) {
  // Should check that index >=0 and < 2^input.length here.
  // Should also check that input.length <= 31.
  string returnValue = "";
  for (int i = 0; i < input.length; i++) {
    if (i & (1 << i) != 0) // 1 << i is the equivalent of 2^i
      returnValue += input[i];
  }
  return returnValue;
}

然后，如果你需要的话，你可以做一个调用这个函数的循环，就像这样：

for (i = 1; i < (1 << input.length); i++)
  getSubSet(input, i); // this doesn't do anything, but you can add it to a list, or output it as desired.

注意我从 1 而不是 0 开始 - 这是因为索引 0 处的结果将是空字符串。顺便说一句，这实际上首先执行最低有效位，因此您的输出列表将是 'f'、'n'、'fn'、'u'、'fu'、'nu', 'fnu', 但顺序似乎并不重要。

找到给定字符串的每个可能的子集

Find every possible subset given a string

java

string

for-loop

substring

arraylist