基于回溯的句子单词全排列算法内存溢出问题及替代方案咨询
我正在测试一款基于回溯法的句子单词全排列生成算法，输入“orange is sweet”可生成“orange is sweet, is orange sweet, sweet is orange, orange sweet is”等排列。
算法实现
public static void calculatePermutations(String sentence) { // 拆分句子为单词数组 String[] lis = sentence.split(" "); // 存储所有排列结果 List<String[]> permute = new ArrayList<>(); // 生成全排列 generatePermutations(lis, 0, permute); // 遍历打印所有排列 for (String[] i : permute) { System.out.println(String.join(" ", i)); } } // 回溯法生成全排列 public static void generatePermutations(String[] arr, int index, List<String[]> permute) { // 递归终止：已处理完所有单词，保存当前排列 if (index == arr.length) { permute.add(Arrays.copyOf(arr, arr.length)); return; } // 遍历剩余单词，生成排列 for (int i = index; i < arr.length; i++) { // 交换当前位置与i位置的单词 String temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; // 递归处理下一个位置 generatePermutations(arr, index + 1, permute); // 回溯：交换回原位置 temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } // 测试入口 public static void main(String[] args) { String sentence = "sky is blue"; calculatePermutations(sentence); }
该算法在小数据量下正常运行，但处理大量数据时会抛出内存溢出异常：
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.base/java.util.Arrays.copyOf(Arrays.java:3481)
我注意到Arrays.copyOf每次都会生成新的数组实例，其核心源码如下：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object) newType == (Object) Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
提问
- 当需要生成超100万条排列短语时，该算法的最大问题是什么？
- 递归是否是导致问题的诱因之一？
- 有哪些可行的替代优化方案？
解答
1. 核心问题：全量存储排列结果导致内存爆炸
当前算法最致命的问题是将所有排列结果预先存储在List<String[]>中。n个单词的全排列总数是n!，当n≥10时，10! = 3628800，已经超过360万条记录；n=12时，12! = 479001600，接近5亿条。每条排列都是独立的字符串数组，即使字符串本身是共享引用，数组对象的内存开销也会迅速累积，加上Arrays.copyOf不断创建新数组，最终耗尽堆内存触发OutOfMemoryError。
2. 递归不是核心诱因
递归本身不会直接导致内存溢出。回溯法的递归深度等于单词数量n，即使n=20，递归深度也只有20，远低于Java栈的默认阈值（通常是1000以上）。递归栈的内存开销和存储所有排列的内存相比可以忽略不计，真正的问题还是结果的全量存储。
3. 优化方案
方案1：生成即处理，不存储全量结果
直接在递归终止阶段（index == arr.length）处理当前排列（比如打印、写入文件、传递给下游逻辑），而不是存入列表。这样内存中始终只保留当前正在构建的数组，内存复杂度从O(n!)降到O(n)。
修改后的核心代码：
public static void calculatePermutations(String sentence) { String[] lis = sentence.split(" "); generatePermutations(lis, 0); } public static void generatePermutations(String[] arr, int index) { if (index == arr.length) { // 直接处理当前排列，无需存储 System.out.println(String.join(" ", arr)); return; } for (int i = index; i < arr.length; i++) { // 交换 String temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; generatePermutations(arr, index + 1); // 回溯交换 temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } }
方案2：迭代式回溯（替代递归）
如果担心极端场景下递归栈的微小开销，可以用迭代方式模拟回溯逻辑，本质还是生成即处理，只是用循环和栈结构替代递归调用。
方案3：分批次处理（需存储部分结果时）
如果业务必须存储部分结果，可以分批次生成、处理、清理：比如每生成1万条排列就写入文件并清空临时存储，再继续生成下一批。但这种方式复杂度较高，优先推荐生成即处理。
方案4：Java Stream惰性生成
利用Java 8+的Stream API实现惰性求值，避免一次性加载所有排列到内存：
public static Stream<String> permutationStream(String[] words) { return permuteStream(words, 0); } private static Stream<String> permuteStream(String[] words, int index) { if (index == words.length - 1) { return Stream.of(String.join(" ", words)); } Stream<String> result = Stream.empty(); for (int i = index; i < words.length; i++) { swap(words, index, i); result = Stream.concat(result, permuteStream(words, index + 1)); swap(words, index, i); } return result; } private static void swap(String[] arr, int i, int j) { String temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 使用示例 public static void main(String[] args) { String[] words = "sky is blue".split(" "); permutationStream(words).forEach(System.out::println); }
Stream会按需生成排列，不会一次性把所有结果加载到内存。
内容的提问来源于stack exchange，提问作者Ger
