日期:2014-05-20  浏览次数:20615 次

Java一个程序
.设计一个可进行数字排列的程序,给出正整数n,则1到n这n个数可以构成n!种排列,把这些排列按照从小到大的顺序(字典顺序)列出,如n=3时,列出1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1六个排列。 具体要求:
(1)输入一个数(做为n),例如3;回车后,再输入一个数例如5(做为m);
(2)根据输入的n输出排列,输出排列中第m(第一步中输入的数)个排列(第1个排列视为第0个排列,例如1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1六个排列中第2个排列是213)

请大虾帮个忙

------解决方案--------------------
有难度啊!
------解决方案--------------------
个人思路:(应该有很多不完善的地方,因为没实际做,有错误见谅哈)
一个list1存储1-n的所有整数,
一个list2存储所有结果(用TreeSet也可以,用set最后查询的时候麻烦,同时set里面要传一个自定义的比较器进去(字符串转成数字比较大小))

过程:
list2的长度小于n!的时候:
每次list1随机排序,转成string拿出来
list2先判断下有没有,有的话不放,没有的话塞进去.

排序:
Collections.sort(list2,指定比较器),比较器比较的是把str转成数字比较大小

拿出来:根据下标拿出来就好
------解决方案--------------------
比较传统的做法就是把全排都写出来编好序
在根据参数读出第几个
但这样做比较浪费空间和时间
上次和朋友讨论过这个问题
最后得出是
可以根据编号反算出数据
理论是可以的
但我们也只是讨论了下 没具体写代码
楼主可以尝试下
------解决方案--------------------
Java code

public static void printNumber(int maxNum, int id){
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        long size = 1;    
        for(int i =1;i<=maxNum;i++){
            size = size*i;
            list1.add(""+i);
        }
        while(list2.size()<size){
            Collections.shuffle(list1);
            StringBuffer sb = new StringBuffer();
            for(int i = 0;i<list1.size();i++){
                sb.append(list1.get(i));
            }
            if(list2.contains(sb.toString())==false){
                list2.add(sb.toString());
            }
        }
        Collections.sort(list2);
        System.out.println(list2.get(id-1));
        
    }

------解决方案--------------------
4楼的方法理论上可行...实现的话要考虑很多阶乘的问题

举例:在n个数排序中找第m个
先一个list存储1-n
一个结果StringBuffer sb

以list[0]开头的有(list.size()-1)!个
以list[1]开头的有(list.size()-1)!个....

用x=m/(n-1)!就知道第几位数,在list中移除这个数,并加在sb 上
同时m = m-x*(n-1)!

又转化成在n-1个元素的全阶乘中找第m-x*(n-1)!个


一直这样做下去知道list.size()=2,找第1个还是第2个,就可以返回结果;



举例:

在3个数的全排列找第五个:
m=5;
list存放{1、2、3}

5/(3-1)! = 2,拿出第二个下标的数=3 ,同时m=5-2*(3-1)! = 1,list移除3剩下{1,2}

转成从{1,2}的排列中找第一个,肯定是12

得出结果312

例2:在4个元素中找第7个
m=7; list存{1,2,3,4}
7/3! = 1,拿出第一个数字为2,m=7-1*3!= 1,list移除2剩下{1,3,4}

1/2!=0,拿出第0个数字为1,m=1-0*2!=1,list移除1剩下{3,4}

在{3,4}的排列中找第一个,结果34

所以最后结果为2134


程序我就不写了,这个不大容易理解






------解决方案--------------------
不明白