排列

Question

数学中有一个排列就是n！的那个，
谁能用Java实现它
要求：（用单词internationalization为例）
1.首先假设这个单词的所有的字母顺序均被无序打乱；
2.将这个单词的所有字母重新排列成各种各样的组合；
3.这些排列必须是取尽全部的；
4.将所有的排列放到一个List中。

Answer 1

举个列子，比如java这个单词
有24中排列，要把这个单词的24中排列放到List中
也就是把java，java，jvaa，aajv等放到List中

Answer 2

import java.util.HashSet;
import java.util.Set;class Test {
    static int size;
    static int count;
    static char[] arrChar = new char[100];
    //如果重复的数据也要把Set改成List
    static Set<String> list = new HashSet<String>();
//    static List<String> list = new ArrayList<String>();    public static void main(String[] args) {        String string = "java";
        size = string.length(); // find its size
        count = 0;
        for (int j = 0; j < size; j++)
            arrChar[j] = string.charAt(j);
        doAnagram(size);
        //List
//        for (int i = 0; i < list.size(); i++) {
//            System.out.println(i+1+":"+list.get(i));
//        }
        //Set
        Object[] display=list.toArray();
        for (int i = 0; i < display.length; i++) {
            System.out.println(i+1+":"+display[i]);
        }
    } 
    public static void doAnagram(int newSize) {
        if (newSize == 1) 
            return; 
        for (int i = 0; i < newSize; i++)
        {
            doAnagram(newSize - 1);
            if (newSize == 2){
                String s = "";
                for (int j = 0; j < size; j++){
                    s+=arrChar[j];
                }
                list.add(s);
            }
            rotate(newSize);
        }
    }    public static void rotate(int newSize) {
        int j;
        int position = size - newSize;
        char temp = arrChar[position];
        for (j = position + 1; j < size; j++)
            arrChar[j - 1] = arrChar[j];
        arrChar[j - 1] = temp; 
    }
}

Answer 3

这个对internationalization这个单词无效
不信你试试，你这个对于单词比较短的可以，长的就不行了

Answer 4

import java.util.ArrayList;
import java.util.List;public class Test { private List<String> result = new ArrayList<String>();

/**
 * @return the result
 */
public List<String> getResult() {
return result;
} /**
 * @param result the result to set
 */
public void setResult(List<String> result) {
this.result = result;
} public static void main(String[] args) {
Test test = new Test();
String token = "monkey";
test.perm(token.getBytes(), 0, token.length() - 1);
System.out.println(test.getResult().size());
} public void perm(byte list[], int k, int m) 
{     
    int i;     
    if(k > m) {          
     StringBuffer sb = new StringBuffer();
        for(i = 0; i <= m; i++) {
         sb.append(list[i]);
        }
        result.add(sb.toString());
    } else {         
        for(i = k; i <= m; i++) {      
         byte temp;
         temp = list[k];
         list[k] = list[i];
         list[i] = temp;
        perm(list, k + 1, m);             
        temp = list[k];
         list[k] = list[i];
         list[i] = temp;         
        }     
    } 
}
}
20的阶乘估计算不出来~~~ 不过这是全排列的的置换算法。效率肯定没问题

Answer 5

晕 弄了半天你想匹配单词~~  用KMP吧

Answer 6

class Test {    public static void main(String[] args) {        String string = "internationalization";
        doAnagram(string.toCharArray(), 0, string.length() - 1);
    }    public static void doAnagram(char[] c, int start, int end) {
        char temp;
        if (start == end) {
            for (int i = 0; i <= end; i++)
                System.out.print(c[i]);
            System.out.println();
        } else {
            for (int i = start; i <= end; i++) {
                temp = c[start];
                c[start] = c[i];
                c[i] = temp;
                doAnagram(c, start + 1, end);
                temp = c[start];
                c[start] = c[i];
                c[i] = temp;
            }
        }
    }
}你可以试试这个，看看要打印多久

Answer 7

justlearn,你真他么虚伪，盗用15楼wt_yao_monkey的知识产权，还振振有词，虚伪至极，没算对就勇敢承认，抄袭别人干什么？严重鄙视你

Answer 8

import java.util.ArrayList;
import java.util.List;public class Test { private List<String> result = new ArrayList<String>();

/**
 * @return the result
 */
public List<String> getResult() {
return result;
} /**
 * @param result the result to set
 */
public void setResult(List<String> result) {
this.result = result;
} public static void main(String[] args) {
Test test = new Test();
String token = "monkey";
test.perm(token.toCharArray(), 0, token.length() - 1);
for( String temp : test.getResult() ) {
System.out.println(temp);
}
} public void perm(char list[], int k, int m) 
{     
    int i;     
    if(k > m) {          
     StringBuffer sb = new StringBuffer();
        for(i = 0; i <= m; i++) {
         sb.append(list[i]);
        }
        result.add(sb.toString());
    } else {         
        for(i = k; i <= m; i++) {      
         char temp;
         temp = list[k];
         list[k] = list[i];
         list[i] = temp;
        perm(list, k + 1, m);             
        temp = list[k];
         list[k] = list[i];
         list[i] = temp;         
        }     
    } 
}
}
刚才不该用byte，用char~ 我在我电脑上测试9位 不用3秒 去掉for( String temp : test.getResult() ) {
System.out.println(temp);
}更快

Answer 9

i18n
18!超过Integer.MAX_VALUE，接近Long.MAX_VALUE，因此，基于数组的方案都不可行

Answer 10

else {         
            for(i = k; i <= m; i++) {      
                char temp;
                temp = list[k];
                list[k] = list[i];
                list[i] = temp;
                perm(list, k + 1, m);             
                temp = list[k];  
                list[k] = list[i];
                list[i] = temp;         
            }     
        } 
perm(list, k + 1, m);后面的三行代码可以去掉，因为递归算法程序是不会执行到后面的；