改进一个求组合数的算法！
刚写了个求数字组合的程序，
比如
Please input the number:
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
TotalCount is :6
Please input the number:
4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
TotalCount is :24
即每一行任意数字都不相等，感觉写得较勉强，算法不太好，用递归写的。请各位给个比较好的算法？下面是我的代码，用java写的。
import java.util.Scanner;
public class Myarrange {
public class Arrint {
int num;// 需进行排列组合的元素。
boolean bool;// 当前元素是否被使用。
Arrint(int k) {
num = k;
bool = false;
}
}
public class workItem {
int num; // 当前存储的数字
boolean bool; // 当前数据是否是有效的
workItem(int k) {
num = k;
bool = false;
}
}
int TotalCount = 0;// 组合的总数
boolean isFirstline = true;
Arrint[] arrint;// 需要进行组合的数据，初始化在构造函数中完成。
int count = 0;// 计数器，用于处理第一行数据的处理，因为第一行数据的处理规则和其它行有所不同。
workItem[] work;
public Myarrange(int k) {
arrint = new Arrint[k + 1];
work = new workItem[k + 1];
for (int i = 0; i < arrint.length; i++) {
arrint[i] = new Arrint(i);
work[i] = new workItem(0);
}
}
boolean check(Arrint[] arr) {
for (int i = 1; i <= arr.length - 1; i++) {
if (arr[i].bool == false) {
return false;
}
}
return true;
}
int minCanused() {
for (int i = 1; i < arrint.length; i++) {
if (arrint[i].bool == false)
return arrint[i].num;
}
return 0;
}
int maxCanused() {
for (int i = arrint.length - 1; i > 0; i--) {
if (arrint[i].bool == false) {
return arrint[i].num;
}
}
return 0;
}
int minNotlessthanCanused(int k) {
for (int i = 1; i < arrint.length; i++) {
if (arrint[i].bool == false && arrint[i].num > k)
return arrint[i].num;
}
return 0;
}
void comb(int level, int k) {
int temp;
while (true) {
if (isFirstline == true) {
count++;
work[level].num = minCanused();
work[level].bool = true;
arrint[work[level].num].bool = true;
} else if ((temp = minNotlessthanCanused(work[level].num)) != 0
&& work[level].bool == true) {
arrint[temp].bool = true;
arrint[work[level].num].bool = false;
work[level].num = temp;
work[level].bool = true;
} else {
work[level].num = minCanused();
work[level].bool = true;
arrint[work[level].num].bool = true;
}
if (check(arrint)) {
TotalCount++;
print(work);
} else {
comb(level + 1, k);
}
if (level == k) {// 当到达一行最后一个元素时，回退至上层
arrint[work[level].num].bool = false;// 将当前层的工作数组中的元素状态置成未使用状态
work[level].bool = false; // 将当前工作数组中的数据元素置为无效数据
if (count == k)
isFirstline = false;// 如果第一行已经输出完毕，将状态标置置为false;
break;
}
if (work[level].num < maxCanused()) {// 如果当前元素比可用数字中的最大数字小的话那么在可用数字中重新挑选一个作为当前数字。
continue;
} else {
arrint[work[level].num].bool = false;
work[level].bool = false;
break;
}
}
}
void print(workItem[] a) {
for (int i = 1; i < a.length; i++) {
System.out.printf( "%6d ", a[i].num);
}
System.out.println();
}
public static void main(String[] args) {
System.out.println( "Please input the number: ");
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
Myarrange Myarr = new Myarrange(i);
// Myarr.printFirstline(i);
Myarr.comb(1, i);
System.out.println( "TotalCount is : " + Myarr.TotalCount);
}
}
[解决办法]
搞错，应该是这个才对
public class test{
String[] list;
StringBuffer sb = new StringBuffer();
test(String in){
int temp = Integer.parseInt(in);
list = new String[temp];
for(int i=0;i <temp;i++)
list[i] = String.valueOf(i+1);
printList(0,list);
System.out.println(sb);
}
String[] replaceStr(String[] s,int c1,int c2){
String temp = s[c1];
s[c1] = s[c2];
s[c2] = temp;
return s;
}
void printList(int start,String[] temparr){
if(start==list.length-1)
for(int i=0;i <temparr.length;i++)
sb.append(temparr[i]+(i==temparr.length-1? " ": " "));
else
for(int i=start;i <list.length;i++)
printList(start+1,replaceStr(temparr.clone(),start,i));
}
public static void main(String args[]){
long t1 = System.currentTimeMillis();
new test(args[0]);
System.out.println(System.currentTimeMillis()-t1);
}
}
但是，用了stringbuffer之后，需要大量内存，所以不可行
再改回使用print输出
public class test{
String[] list;
test(String in){
int temp = Integer.parseInt(in);
list = new String[temp];
for(int i=0;i <temp;i++)
list[i] = String.valueOf(i+1);
printList(0,list);
}
String[] replaceStr(String[] s,int c1,int c2){
String temp = s[c1];
s[c1] = s[c2];
s[c2] = temp;
return s;
}
void printList(int start,String[] temparr){
if(start==list.length-1)
for(int i=0;i <temparr.length;i++)
System.out.print(temparr[i]+(i==temparr.length-1? " ": " "));
else
for(int i=start;i <list.length;i++)
printList(start+1,replaceStr(temparr.clone(),start,i));
}
public static void main(String args[]){
new test(args[0]);
}
}
用时400毫秒，不受内存的限制
