java全排列递归算法怎么应用

59次阅读

共计 1116 个字符，预计需要花费 3 分钟才能阅读完成。

全排列是一种经典的组合数学问题，递归算法可以很好地解决该问题。下面是一种 Java 递归算法实现全排列的例子：

import java.util.ArrayList;
public class Permutations {public static void main(String[] args) {int[] nums = {1, 2, 3};
ArrayList> result = permute(nums);
System.out.println(result);
}
public static ArrayList> permute(int[] nums) {ArrayList> result = new ArrayList();
ArrayList tempList = new ArrayList();
permuteHelper(nums, tempList, result);
return result;
}
private static void permuteHelper(int[] nums, ArrayList tempList, ArrayList> result) {if (tempList.size() == nums.length) {result.add(new ArrayList(tempList));
} else {for (int i = 0; i < nums.length; i++) {if (tempList.contains(nums[i])) {continue;}
tempList.add(nums[i]);
permuteHelper(nums, tempList, result);
tempList.remove(tempList.size() - 1);
}
}
}
}

在上面的代码中，permute()方法是入口方法，它会创建一个空的结果列表和一个空的临时列表，然后调用 permuteHelper() 方法进行递归。permuteHelper()方法有三个参数：原始数组 nums、临时列表tempList 和结果列表 result。
在permuteHelper()方法中，首先判断临时列表的大小是否等于原始数组的大小，如果是，则将临时列表添加到结果列表中。如果不是，则循环遍历原始数组中的每个元素，如果临时列表中已经包含该元素，则跳过该循环，否则添加该元素到临时列表中，然后递归调用 permuteHelper() 方法，再将临时列表的最后一个元素移除，以便进行下一次循环。
最终，当临时列表的大小等于原始数组的大小时，所有可能的排列都已经生成，将临时列表添加到结果列表中，并返回结果列表。
以上就是一个简单的 Java 递归算法实现全排列的例子。该算法的时间复杂度为 O(n!)，其中 n 为原始数组的大小。

丸趣 TV 网 – 提供最优质的资源集合！

正文完