请教一个算法的问题，先谢谢大家了

这是和我的一个好友大bug学习的！import java.util.ArrayList;
import java.util.Arrays;
public class Permutation {
    public static void main(String[] args) {
        String[] strs=permutation("12345");
        System.out.println("全部排列的个数为："+strs.length+"个");
        System.out.println("全部排列的元素是：");
        System.out.println(Arrays.toString(strs));
    }

    public  static String[] permutation(String str) {
        ArrayList<String> myList = new ArrayList<String>();
        char[] strChars=str.toCharArray();
        char temp;
        long times=1;
        int pos=strChars.length-2;
        int increment=-1;
        for(int i=1;i<strChars.length+1;i++){
            times*=i;
        }
        for(int i=1;i<times;i++){
            temp=strChars[pos];
            strChars[pos]=strChars[pos+1];
            strChars[pos+1]=temp;
            myList.add(new String(strChars));
            pos+=increment;
            if(pos==-1){
                increment=1;
                pos=0;
                temp=strChars[strChars.length-2];
                strChars[strChars.length-2]=strChars[strChars.length-1];
                strChars[strChars.length-1]=temp;
                myList.add(new String(strChars));
                i++;
            }else if(pos==strChars.length-1){
                increment=-1;
                pos=strChars.length-2;
                temp=strChars[0];
                strChars[0]=strChars[1];
                strChars[1]=temp;
                myList.add(new String(strChars));
                i++;
            }
        }
        return myList.toArray(new String[0]);
    }

}  结果：
全部排列的个数是：120个
全部排列的元素是：
[12354, 12534, 15234, 51234, 51243, 15243, 12543, 12453, 12435, 21435, 21453, 21543, 25143, 52143, 52134, 25134, 21534, 21354, 21345, 12345, 12354, 12534, 15234, 51234, 51243, 15243, 12543, 12453, 12435, 21435, 21453, 21543, 25143, 52143, 52134, 25134, 21534, 21354, 21345, 12345, 12354, 12534, 15234, 51234, 51243, 15243, 12543, 12453, 12435, 21435, 21453, 21543, 25143, 52143, 52134, 25134, 21534, 21354, 21345, 12345, 12354, 12534, 15234, 51234, 51243, 15243, 12543, 12453, 12435, 21435, 21453, 21543, 25143, 52143, 52134, 25134, 21534, 21354, 21345, 12345, 12354, 12534, 15234, 51234, 51243, 15243, 12543, 12453, 12435, 21435, 21453, 21543, 25143, 52143, 52134, 25134, 21534, 21354, 21345, 12345, 12354, 12534, 15234, 51234, 51243, 15243, 12543, 12453, 12435, 21435, 21453, 21543, 25143, 52143, 52134, 25134, 21534, 21354, 21345, 12345]

package test;import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;public class MyTest {
public static void main(String[] args) {
MyTest mt = new MyTest();

mt.init("123");
mt.productStr();
mt.printTarStrings(); }
//字串源
private String srcString;
//结果集
private List<String> tarStrings;

//初始化成员变量
public void init(String srcString)
{
this.srcString = srcString;
this.tarStrings = new LinkedList<String>();
}

//清理
public void clear()
{
this.srcString = null;
this.tarStrings = null;
}

//拷贝StringBuffer
private StringBuffer copySB(StringBuffer sb)
{
return new StringBuffer(sb);
}

//产生结果字符串
public void productStr()
{
StringBuffer srcSB = new StringBuffer(srcString);
StringBuffer childSB = new StringBuffer();
productStr(srcSB,childSB);
}

//核心算法
private void productStr(StringBuffer srcSB,StringBuffer childSB)
{
if(0 == srcSB.length())
{
this.tarStrings.add(childSB.toString());
}
else
{
for(int i=0;i<srcSB.length();i++)
{
StringBuffer newSrcSB = copySB(srcSB);
StringBuffer newChildSB = copySB(childSB);

newChildSB.append(newSrcSB.charAt(i));
newSrcSB.deleteCharAt(i);

productStr(newSrcSB,newChildSB);

}
}
}

//获得结果
public List<String> getTarStrings() {
return tarStrings;
}

//打印结果
public void printTarStrings()
{
for(Iterator it = this.tarStrings.iterator();it.hasNext();)
{
System.out.println(it.next());
}
}}

这个算法效率不是很高但是结构清晰容易理解如果考虑到数字有重复得情况也很好办，把核心算法中的if判断条件
if(0 == srcSB.length())
修改为
if(0 == srcSB.length()&&!this.tarStrings.contains(childSB.toString()))
就可以了
也就是说添加之前判断下tarStrings中是否已经存在一样的字串了

import java.util.HashSet;
import java.util.Set;
public class Sequence {
private static Set<String> strSet = new HashSet<String>();
private String sb="";

int[][] ;
boolean[] lock;
public void printSequence(String str){
char[] chaArr = str.toCharArray();
int lenght = chaArr.length;
= new int[lenght][lenght];
lock = new boolean[lenght];
for(int i=0;i<lenght;i++)
for(int j=0;j<lenght;j++)
[i][j] = 1;
for(int i=0;i<lenght;i++){
lock[i] = false;
}

for(int i=0;i<lenght;i++){
listSequence(chaArr,i,lenght);
}
}

public void listSequence(char[] charArr,int i,int lenght){
sb+=charArr[i];
if(sb.length()==lenght)
strSet.add(sb);
lock[i]=true;
for(int j=0;j<lenght;j++){
if([i][j]==1&&!lock[j]){
listSequence(charArr,j,lenght);
}
}
sb = sb.substring(0, sb.length()-1);
lock[i]=false;
}

public static void main(String[] args){
Sequence se = new Sequence();
se.printSequence("1234");
for(String str:strSet){
System.out.println(str);
}
System.out.println("长度是："+strSet.size());

}
}

非递归,交换法求
[code=Java/C++]public class Main {
    public static void main(String[] args) throws Exception {
        String s = "1234";
        String[] list = plpringf(s.toCharArray());
        for (int i = 0, im = list.length; i < im; i++) { //输出
            System.out.println("第" + (i + 1) + "个: " + list[i]);
        }
    }
    public static String[] plpringf(char[] d) {
        if (d == null || d.length < 2 || d.length > 16) {
            return null;
        }
        int sw = 1;
        for (int i = 1, im = d.length; i <= im; i++) {//计算交换次数
            sw *= i;
        }
        char list[][] = new char[sw + 1][d.length];
        list[0] = copy(d);
        int len = 1;
        for (int i = d.length - 2, ep = d.length - 1, dlen = d.length; i > -1; i--) {//要进行有序化的位置
            for (int k = 0, km = len; k < km; k++) {//
                for (int j = i + 1; j < dlen; j++) {
                    //System.arraycopy(list[k], 0, list[len], 0, dlen);
                    list[len] = copy(list[k]);//复制list[k]的数据到list[len]
                    char c = list[len][i];             //交换
                    list[len][i] = list[len][j];
                    list[len][j] = c;
                    if (!equals(list, len, list[len])) {//不包含相同则添加进去
                        len++;
                    }
                }
            }
        }
        String[] re = new String[len];
        for (int i = 0; i < len; i++) {      //将数组转成字符串
            re[i] = new String(list[i]);
        }
        return re;
    }
    static char[] copy(char[] d) {
        char[] c = new char[d.length];
        for (int i = d.length - 1; i > -1; i--) {
            c[i] = d[i];
        }
        return c;
    }
    static boolean equals(char[][] list, int len, char[] c) {//
        boolean flag = false;
        for (int i = len - 1; i > -1; i--) {
            for (int j = c.length - 1; j > -1; j--) {
                if (list[i][j] != c[j]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                flag = false;
            } else {
                return true;
            }
        }
        return false;
    }
}[/code]

这个是用排列组合做的。代码简洁。应该符合你的要求 --->
package com.test;public class test {
public static void main(String[] args) {
String s = "122345";
char[] c = s.toCharArray();
new test().zuhe(c, c.length, 0);
System.out.print("可能的组合数：" + kk);
}
static int kk = 0;
private void zuhe(char[] array, int n, int k) {
if (n == k) {
String str = new String(array);
System.out.println(str);
++kk;
} else {
for (int i = k; i < n; i++) {
swap(array, k, i);
zuhe(array, n, k + 1);
swap(array, i, k);
}
}
}
private void swap(char[] a, int x, int y) {
char temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}

用栈实现的经典写法完全符合你的要求
public class Arrangement { public static void go(int[] data) {
go(data, new boolean[data.length], new int[data.length], 0);
} public static void go(int[] data, boolean[] state, int[] flag, int p) {
print(p, data, flag); for (int i = 0; i < data.length; i++) {
if (!state[i]) {
state[i] = true;
flag[p] = i; // 或者 flag[i] = p; 都可以
go(data, state, flag, p + 1);
state[i] = false;
}
}
} public static void print(int p, int[] data, int[] flag) {
if (p >= data.length) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[flag[i]] + " ");
}
System.out.println();
}
} public static void main(String[] args) {
int[] data = { 1, 2, 3 };
go(data);
}
}
不知道你说的解决重复是什么意思.
如果是去重复数据,放到set里就行.
如果不用去,用我这个方法就行.

调试易

请教一个算法的问题，先谢谢大家了

解决方案 »