在 Java 中使用 ArrayList 进行字符串及其子字符串的排列

Question

我被要求编写一个程序来使用 ArrayList 查找字符串及其子字符串的排列。我想出了一个解决方案，但它没有显示所需的输出。因此，如果有人能在这方面启发我一点，我将不胜感激。

问题如下：

计算字符串及其子字符串的所有排列。例如，给定一个字符串 S，例如“abc”，它应该输出一个字符串列表/数组 retlist [a, b, c, ab, ba, ac, ca, bc, cb, abc, acb, bac, bca,出租车，CBA]。您的代码应该将 S 作为输入，并为排列列表生成 retlist。除了拥有有效的代码之外，请优化代码以提高速度和内存效率（我们将测试大字符串，速度越快越好）。

正如问题中所说，当排列“abc”字符串时，它应该打印如下结果：

[a、b、c、ab、ba、ac、ca、bc、cb、abc、acb、bac、bca、cab、cba]

到目前为止我想到的：

import java.util.ArrayList;
import java.util.List;

public class Permutation {

    public static void main(String[] args) {
        enumerateSubString("abc");
    }

    public static List<String> enumerateSubString(String S_input) {
        ArrayList<String> retlist = new ArrayList<String>();

        int n = S_input.length();

        if (n == 1) {
            retlist.add(S_input);
        } else {
            for (int i = 0; i < n; i++) {
                retlist.addAll(enumerateSubString(S_input.substring(0, i) + S_input.substring(i + 1, n)));
            }
        }

        System.out.print(retlist);
        return retlist;
    }
}

我现在用上面的代码得到的结果：

[c][b][c, b][c][a][c, a][b][a][b, a][c, b, c, a, b, a]

谢谢

Answer 1

使用通用算法添加另一个答案。这将按照提到的顺序给出所有排列。希望这能解决目的

public class Test {

public static void main(String[] args) {

    String s = "abc";

    Map<Integer, List<String>> map = new HashMap<>();

    List<String> strArray = new ArrayList<String>(Arrays.asList(s.split("")));
    map.put(1, strArray);

    if (strArray.size() > 1) {
        new Test().enumerateSubString(strArray.size(), map);
    }
    System.out.println(map.values());
}

public void enumerateSubString(int n, Map<Integer, List<String>> map) {

    if (!map.containsKey(n)) {
        map.put(n, new ArrayList<>());
    }

    if (n == 2) {
        // List of string with each having 1 character
        List<String> list_1 = map.get(1);
        // List of string which each having 2 characters
        List<String> list_2 = new ArrayList<>();
        for (int i = 0; i < list_1.size(); i++) {
            for (int j = i + 1; j < list_1.size(); j++) {
                list_2.add(list_1.get(i) + list_1.get(j));
                list_2.add(swap(list_1.get(i) + list_1.get(j)));
            }
        }
        // Map list_2 to key 2
        map.put(n, list_2);
    } else {
        // Recursive function
        enumerateSubString(n - 1, map);
        // List of string with each having n-1 characters
        List<String> list = map.get(n - 1);
        // List of string with each having n characters
        List<String> list_n = map.get(n);
        // Add each character to list of n-1 to get n charater string list
        for (String l1 : map.get(1)) {
            for (String l : list) {
                // this condition is to avoid repetation of charaters n
                // String
                if (l.indexOf(l1) < 0) {
                    list_n.add(l1 + l);
                }
            }
        }
    }
}

// Function to swap characters
private String swap(String str) {
    String s1 = str.substring(1) + str.substring(0, 1);
    return s1;
}}

Answer 2

public static void main(String args[]) {

    String word = "abc";
    // ,acb,bac,bca,cab,cba
    int n = word.length();

    combination(word, "");
    System.out.println(list.stream().collect(Collectors.toList()));
}

private static void combination(String str, String ans) {
    if (str.length() >= 0) {
        if (!ans.isEmpty()) {
            list.add(ans);
        }
    }

    for (int i=0; i<str.length(); i++) {

    

char ch=str.charAt(i);
        String remaining =str.substring(0,i)+str.substring(i+1);
        combination(remaining, ans + ch);
    }
}