「java全排列递归算法」排列组合递归算法
今天给各位分享java全排列递归算法的知识，其中也会对排列组合递归算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
java中递归算法是怎么算的？
1.汉诺塔问题
import javax.swing.JOptionPane;
public class Hanoi {
private static final String DISK_B = "diskB";
private static final String DISK_C = "diskC";
private static final String DISK_A = "diskA";
static String from=DISK_A;
static String to=DISK_C;
static String mid=DISK_B;
public static void main(String[] args) {
String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");
int num=Integer.parseInt(input);
move(num，from，mid，to);
}
private static void move(int num， String from2， String mid2， String to2) {
if(num==1){
System.out.println("move disk 1 from "+from2+" to "+to2);
}
else {
move(num-1，from2，to2，mid2);
System.out.println("move disk "+num+" from "+from2+" to "+to2);
move(num-1，mid2，from2，to2);
}
}
}
2. 这是一个排列的例子，它所做的工作是将输入的一个字符串中的所有元素进行排序并输出，例如：你给出的参数是"abc" 则程序会输出：
abc
acb
bac
bca
cab
cba
(1)算法的出口在于：low=high也就是现在给出的排列元素只有一个时。
(2)算法的逼近过程：先确定排列的第一位元素，也就是循环中i所代表的元素，
然后low+1开始减少排列元素，如此下去，直到low=high
public static void permute(String str) {
char[] strArray = str.toCharArray();
permute(strArray， 0， strArray.length - 1);
}
public static void permute(char[] list， int low， int high) {
int i;
if (low == high) {
String cout = "";
for (i = 0; i= high; i++)
cout += list[i];
System.out.println(cout);
} else {
for (i = low; i= high; i++) {
char temp = list[low];
list[low] = list[i];
list[i] = temp;
permute(list， low + 1， high);
temp = list[low];
list[low] = list[i];
list[i] = temp;
}
}
}
3。这是一个组合的例子，与上述的例子相似，只是它所做的工作是，输出所给字符串中制定数目的元素的组合种类
(1)程序出口在于n=1，此时只要输出目标数组的所有元素即可
(2)逼近过程，当n1 的时候，我们先取第一个元素放入目标数组中，然后n-1，如此下去，最后出来。
import javax.swing.JOptionPane;
public class Combination {
/**
* @param args
*/
public static void main(String[] args) {
String input = JOptionPane.showInputDialog("please input your String： ");
String numString = JOptionPane.showInputDialog("please input the number of your Combination： ");
int num = Integer.parseInt(numString);
Combine(input， num);
}
private static void Combine(String input， int num) {
char[] a = input.toCharArray();
String b = "";
Combine(a， num， b， 0， a.length);
}
private static void Combine(char[] a， int num， String b， int low， int high) {
if (num == 0) {
System.out.println(b);
} else {
for (int i = low; ia.length; i++) {
b += a[i];
Combine(a， num - 1， b， i+1， a.length);
b=b.substring(0， b.length()-1);
}
}
}
}
java中，用递归方法求n个数的无重复全排列，n=3。
程序如下所示，输入格式为：
5
3 1 2 1 2
第一行是数字个数，第二行有n个数，表示待排列的数，输入假设待排序的数均为非负数。
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static final int maxn = 1000;
int n; // 数组元素个数
int[] a; // 数组
boolean[] used; // 递归过程中用到的辅助变量，used[i]表示第i个元素是否已使用
int[] cur; // 保存当前的排列数
// 递归打印无重复全排列，当前打印到第idx位
void print_comb(int idx) {
if(idx == n) { // idx == n时，表示可以将cur输出
for(int i = 0; i n; ++i) {
if(i 0) System.out.print(" ");
System.out.print(cur[i]);
}
System.out.println();
}
int last = -1; // 因为要求无重复，所以last表示上一次搜索的值
for(int i = 0; i n; ++i) {
if(used[i]) continue;
if(last == -1 || a[i] != last) { // 不重复且未使用才递归下去
last = a[i];
cur[idx] = a[i];
// 回溯法
used[i] = true;
print_comb(idx + 1);
used[i] = false;
}
}
}
public void go() throws FileNotFoundException
{
Scanner in = new Scanner(new File("data.in"));
// 读取数据并排序
n = in.nextInt();
a = new int[n];
for(int i = 0; i n; ++i) a[i] = in.nextInt();
Arrays.sort(a);
// 初始化辅助变量并开始无重复全排列
cur = new int[n];
used = new boolean[n];
for(int i = 0; i n; ++i) used[i] = false;
print_comb(0);
in.close();
}
public static void main(String[] args) throws FileNotFoundException{
new Main().go();
}
}
客观来说，非递归的无重复全排列比较简单且高效。
java全排列递归算法
思路:先有一个起始排列，如1234.从后面扫描，直到找到a[k],a[k]a[k+1];再从后面扫描，直到找到a[j],这里有 a[k]a[j]。交换a[k],a[j].再把a[k+1],...a[n-1]排序（从小到大），即得到了一个排列，再循环下去，直到找出所有的排序。用C语言的，参考下:
java全排列 数组
全排列算法很多，这是其中一个，使用递归——
import java.util.ArrayList;
import java.util.List;
public class PermAComb {
static Listint[] allSorts = new ArrayListint[]();
public static void permutation(int[] nums, int start, int end) {
if (start == end) { // 当只要求对数组中一个数字进行全排列时，只要就按该数组输出即可
int[] newNums = new int[nums.length]; // 为新的排列创建一个数组容器
for (int i=0; i=end; i++) {
newNums[i] = nums[i];
}
allSorts.add(newNums); // 将新的排列组合存放起来
} else {
for (int i=start; i=end; i++) {
int temp = nums
今天给各位分享java全排列递归算法的知识，其中也会对排列组合递归算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
; // 交换数组第一个元素与后续的元素nums
今天给各位分享java全排列递归算法的知识，其中也会对排列组合递归算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
= nums[i];nums[i] = temp;
permutation(nums, start + 1, end); // 后续元素递归全排列
nums[i] = nums
今天给各位分享java全排列递归算法的知识，其中也会对排列组合递归算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
; // 将交换后的数组还原nums
今天给各位分享java全排列递归算法的知识，其中也会对排列组合递归算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
= temp;}
}
}
public static void main(String[] args) {
int[] numArray = {1, 2, 3, 4, 5, 6};
permutation(numArray, 0, numArray.length - 1);
int[][] a = new int[allSorts.size()][]; // 你要的二维数组a
allSorts.toArray(a);
// 打印验证
for (int i=0; ia.length; i++) {
int[] nums = a[i];
for (int j=0; jnums.length; j++) {
System.out.print(nums[j]);
}
System.out.println();
}
System.out.println(a.length);
}
}
java全排列递归算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于排列组合递归算法、java全排列递归算法的信息别忘了在本站进行查找喔。
发布于：2022-12-02，除非注明，否则均为原创文章，转载请注明出处。