JAVA模拟排列组合
发布网友
发布时间:2022-04-26 05:03
我来回答
共3个回答
热心网友
时间:2022-06-20 23:30
全排列-有个递推公式(以[1 2 3 ] 为例):
所有全排列是:
step 1: {1 [2 3]}, {2, [1, 3]}, {3, [1, 2]}
对上面方括号里面的数字再进行如上的求解比如[2 3]
step 2: {2, [3]}, {3, [2]};
当方括号里面的数字只有一个元素的时候, 整个递归过程就返回了, 所以, step 2回到step 1的结果是:
1 2 3
1 3 2
。。。
算法有了 应该自己会写了吧 不过怎么证明这个算法的正确性你可以自己考虑一下:
小提示:
tip 1: n个数字的所有排列有n!种。(已知)
tip 2:证明 以上算法不会出现重复的排列顺序(需要证明的)
tip 3: 证明以上算法最终能得到n!个结果 (需要证明的)
综上tip 1、2、3 可以证明以上算法确实能得到所有元素的全排列。
希望你自己能抽象写出相应的算法。最后强调一点:以上算法得到的结果不是有序的, 要得到有序的结果又两种选择:1. 对以上算法所得的结果进行全排列 2. 不采用递归方法而采用深搜策略。
热心网友
时间:2022-06-20 23:31
public class Test{
static public void swapTwo(final int a[], final int k1, final int k2){
int t=a[k1]; a[k1]=a[k2]; a[k2]=t;
}
static public void permutation(final int a[], final int level, final int n){
if(level==n){
for(int i=0;i<n;i++) System.out.print(a[i]+" ");
System.out.println();
}else for(int i=level;i<a.length;i++){
swapTwo(a, level, i);
permutation(a, level+1, n);
swapTwo(a, i, level);
}
}
public static void main(String[] args) {
int a[]={3,7,9};
permutation(a, 0, 3);
}
}
========
3 7 9
3 9 7
7 3 9
7 9 3
9 7 3
9 3 7
热心网友
时间:2022-06-20 23:31
全排列?
用指针啊追问我是新手来着……
完全不懂啊……
请大侠不吝赐教~~~~~~~~
追答首先你要学会简化代码的结构,这种问题肯定是用递归解决。 递归的第一目标就是要将结构简化到最简。类似于这样
public 递归方法(参数列表){
if(列表的元素只有两个){
输出:“元素一元素二”
输出:“元素二元素一”
}else{
//此时元素有两个以上,这时候要使用递归
递归方法(参数列表)//使用递归方法将元素细分
}
}