Java -获得所有排列，子串和每个子串的排列

Question

首先，我首先要说英语不是我的第一语言，所以我对任何糟糕的解释表示歉意。

我想知道如何获取具有如此多不同顺序的字符串的每个子字符串。在你告诉我这个问题之前已经问过了，我想说的是，我看到的这个任务的几乎每个代码实现都不包含重复项。但是假设我有一个字符串“enviroment”，我想要每个子字符串，包括“ment”，“met”，“ten”，“net”，“note”，“more”e.t.c e.t.c 我将如何实现这一目标？

这是我写的函数。

     public static ArrayList<String> getAllSubstringsOfAString(String inputString)
     {
     ArrayList<String> allSubstrings = new ArrayList<String>();
     String sub;
     for(int i = 0; i < inputString.length(); i++)
     {
        for (int j = 1; j <= inputString.length() - i; j++)
        {
            sub = inputString.substring(i , i + j);
            allSubstrings.add(sub);
        }
      }
      return allSubstrings;
     }

当我运行这个函数时

    public static void main(String[] args) throws IOException {
    ArrayList<String> allSubStrings = getAllSubstringsOfAString("environment");
    for (String allSubString : allSubStrings) {
        System.out.println(allSubString);
    }

它会打印出来

    e
    en
    env
    envi
    envir
    enviro
    environ
    environm
    environme
    environmen
    environment
    n
    nv
    nvi
    nvir
    nviro
    nviron
    nvironm
    nvironme
    nvironmen
    nvironment
    v
    vi
    vir
    viro
    viron
    vironm
    vironme
    vironmen
    vironment
    i
    ir
    iro
    iron
    ironm
    ironme
    ironmen
    ironment
    r
    ro
    ron
    ronm
    ronme
    ronmen
    ronment
    o
    on
    onm
    onme
    onmen
    onment
    n
    nm
    nme
    nmen
    nment
    m
    me
    men
    ment
    e
    en
    ent
    n
    nt
    t

这只是我想要的一小部分。我希望函数能够按每个顺序获取子字符串。例如，如果我想让它包含像“net”、“ten”、“绝不”等字符串，因为它们都是单词“环境”的子字符串。我必须对我的函数进行哪些更改才能实现这一点？

此外，作为一名Java初学者，我想知道我的代码是否写得很好，我可以对代码进行哪些更改，以使其性能更好、外观更好，并遵循常见的Java编码约定。

提前谢谢

Answer 1

下面的程序返回所有可能的子集和它们各自的排列。

• 例如，对于值abcd@1234它将返回986410个可能的值。
• [注意]：对于包含相同字符的排列，它的工作方式不同。
  值的示例aaaa@1234它将返回6850个可能的值。

java prettyprint-override">public class PermutationWithSub {
    public void subStrings(String string){
        List<List<Character>> listList = new ArrayList<>();
        listList.add(new ArrayList<>());
        ArrayList<String> subStringArraylist = new ArrayList<>();
        ArrayList<String> bruteList = new ArrayList<>();
        for (char c:string.toCharArray()){
            int size = listList.size();
            for (int i=0;i<size;i++){
                List<Character> temp = new ArrayList<>(listList.get(i));
                temp.add(c);
                listList.add(temp);
            }
        }
        for (List<Character> characterList : listList) {
            StringBuilder stringBuilder = new StringBuilder();
            for (Character character : characterList) {
                stringBuilder.append(character);
            }
            subStringArraylist.add(stringBuilder.toString());
        }
        for (String str:subStringArraylist){
            List<List<Character>> listListChar = permute(str);
            for (List<Character> listChar:listListChar){
                StringBuilder stringBuilder = new StringBuilder();
                for (Character character:listChar){
                    stringBuilder.append(character);
                }
                bruteList.add(stringBuilder.toString());
            }
        }
        listList.clear();
        subStringArraylist.clear();
        for (String str:bruteList){
                System.out.println(str);
        }
    }
    public List<List<Character>> permute(String string){
        List<List<Character>> powerSet = new ArrayList<>();
        generateSet(powerSet,new ArrayList<>(),string.toCharArray());
        return powerSet;
    }

    private void generateSet(List<List<Character>> powerSet, List<Character> temp, char[] chars) {
        if (temp.size()==chars.length){
            powerSet.add(new ArrayList<>(temp));
        }else {
            for (char aChar : chars) {
                if (temp.contains(aChar))
                    continue;
                temp.add(aChar);
                generateSet(powerSet, temp, chars);
                temp.remove(temp.size() - 1);
            }
        }
    }
    public static void main(String[] args) {
        MyBruteForceTool myBruteForceTool = new MyBruteForceTool();
        myBruteForceTool.subStrings("abcd@1234");
    }
}

Answer 2

在另一个问题的帮助下，我拼凑出了这个问题。

public static void main(String[] args) {
    List<String> list = perms("codes");
    list.forEach(s -> System.out.println(s));
}

public static List<String> perms(String string) {

    List<String> result = new ArrayList<String>();
    char[] values = string.toCharArray();
    for (int width = 1; width <= values.length; width++) { // for every length
        int stack[] = new int[width];
        for (int i = 0; i < stack.length; i++) { // start from a specific point without duplicates
            stack[i] = stack.length - i - 1;
        }
        int position = 0;
        while (position < width) {

            position = 0;
            StringBuilder sb = new StringBuilder();
            while (position < width) { // build the string
                sb.append(values[stack[position]]);
                position++;
            }
            result.add(sb.toString());
            position = 0;
            while (position < width) {
                if (stack[position] < values.length - 1) {
                    stack[position]++;
                    if (containsDuplicate(stack) == false)
                        break;
                    else
                        position = 0;
                } else {
                    stack[position] = 0;
                    position++;
                }
            }
        }
    }
    return result;
}

private static boolean containsDuplicate(int[] stack) {
    for (int i = 0; i < stack.length; i++) {
        for (int j = 0; j < stack.length; j++) {
            if (stack[i] == stack[j] && i != j) {
                return true;
            }
        }
    }
    return false;
}

它不会重复使用单词中的字母，除非这个单词包含两次字母。< br >在这种情况下，会有替身。< br >它不使用递归，所以堆栈溢出不会成为问题。

Answer 3

1）生成所有子字符串（你已经得到了那部分）

2）对于每个子字符串生成它的所有排列 - 您可以使用位向量递归或迭代地执行此操作（此处已在此处显示SO如何操作，快速Google搜索也会给您一些提示）

3） 将所有内容添加到最后的列表中，这将得到您已经拥有的内容、您拥有的内容的反转版本以及所有其他排列

例如，使用“abc”，您将获得：

• a（1 个字符，1 个排列）
• ab（子字符串）
  • BA（子字符串排列）
  • bca（子串置换）
  • bac（子串置换）
  • acb（子串置换）
  • cab（子串置换）
  • 子串置换

  请注意，计算可能需要一些时间，当字符串有 N 时，它有 N！排列，您将为每个子字符串调用它，因此 N 次将产生 O（N*N！） 时间复杂度。

  正如@PM77-1所指出的，如果我们的字符串有重复的子字符串，如abcabc，这可能会做很多不必要的工作。在这种情况下，在每次新的迭代之前，您可以检查给定的子串是否已经在集合中（是的，您可以将结果列表更改为具有O（1）个查找的集合），如果已经存在，则跳过它。