Как использовать хвостовую рекурсию и / или потоки для поиска всех перестановок строки без нехватки памяти для длинных строк - PullRequest
Новая
       1

Как использовать хвостовую рекурсию и / или потоки для поиска всех перестановок строки без нехватки памяти для длинных строк

2 голосов
/ 18 июня 2020

Я написал следующий код для возврата массива всех перестановок строки. Приведет ли это к проблемам с длинными строками? Я подозреваю, например, что Java не сможет использовать хвостовую рекурсию, поскольку рекурсивный вызов не является последним вызовом функции, что, возможно, приведет к переполнению стека. Кроме того, мое решение собирает все возможные перестановки и возвращает их в одном массиве. Поскольку количество перестановок увеличивается с увеличением длины строки, массив не помещается в память для длинных строк. Можно это как-то исправить? Возможно, используя вместо этого Stream? 

public static String[] perms(String str) {
        String[] permutations = new String[factorial(str.length())];
        int permIdx = 0;

        if (str.length() == 1) {
            return new String[]{str};
        }

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            String restOfString = str.substring(0, i) + str.substring(i + 1);
            String[] permutationsOfRestString = perms(restOfString);
            for (String permutation : permutationsOfRestString) {
                permutations[permIdx++] = ch + permutation;
            }
        }

        return permutations;
    }

    public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return n * factorial(--n);
        }
    }

Ответы [ 2 ]

3 голосов
/ 18 июня 2020

Можно создать решение Stream, которое не должно хранить в памяти все строки результатов, например, 

public static Stream<String> perms(String str) {
    if(str.length() <= 1) return Stream.of(str);
    return IntStream.range(0, str.length()).boxed()
        .flatMap(ix -> perms(new StringBuilder(str).deleteCharAt(ix).toString())
            .map(s  -> str.charAt(ix) + s));
}

Шаг рекурсии был заменен шагом flatMap, который будет вычисляться лениво. .

Конечно, материализуется ли это преимущество, зависит от операции терминала, которую вы связываете с потоком. Например, когда вы цепляете toArray(), вы вернетесь на круги своя. Но объединение в цепочку .forEach(System.out::println) будет печатать перестановки без необходимости хранить их все в памяти. String), мы можем опустить операцию toString на промежуточном этапе и передать StringBuilder напрямую. Таким образом, мы одновременно повышаем гибкость метода и производительность. 

public static Stream<String> perms(CharSequence str) {
    if(str.length() <= 1) return Stream.of(str.toString());
    return IntStream.range(0, str.length()).boxed()
        .flatMap(ix -> perms(new StringBuilder(str).deleteCharAt(ix))
            .map(s -> str.charAt(ix)+s));
}
0 голосов
/ 23 июля 2020

Это решение может помочь устранить java .lang.OutOfMemoryError: G C 

public static List<String> generatepermutations(String str) {
    List<Character> chars = new ArrayList<>();
    for (char ch : str.toCharArray()) {
        chars.add(ch);
    }
    List<String> fl = new ArrayList<>();
    for (int i = 0; i < chars.size(); i++) {
        char ch = chars.get(i);
        List<Character> templist = new ArrayList<>();
        chars.stream().forEach(e -> templist.add(e));
        templist.remove(i);
        Collections.sort(templist);
        for (int j = 0; j < chars.size(); j++) {
            templist.add(j, ch);
            String t = templist.toString().replace("[", "").replace("]", "").replace(", ", "");
            fl.add(t);
            templist.remove(j);
        }
    }
    System.out.println(fl);
    return fl;
}
...