Java一个程序

Question

．设计一个可进行数字排列的程序，给出正整数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）请大虾帮个忙

Answer 1

个人思路：（应该有很多不完善的地方，因为没实际做，有错误见谅哈）
一个list1存储1-n的所有整数，
一个list2存储所有结果（用TreeSet也可以，用set最后查询的时候麻烦，同时set里面要传一个自定义的比较器进去（字符串转成数字比较大小））过程：
list2的长度小于n！的时候：
每次list1随机排序，转成string拿出来
list2先判断下有没有，有的话不放，没有的话塞进去.排序:
Collections.sort(list2,指定比较器)，比较器比较的是把str转成数字比较大小拿出来：根据下标拿出来就好

Answer 2

补充：每个组合位数都相同的，这样的话排序的那一步直接sort(list2)就可以了

Answer 3

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));

}

Answer 4

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
程序我就不写了，这个不大容易理解

Answer 5

这个是按4楼的提议写的程序
我的类名叫Test
因为用的是int，所以如果maxNum过大就不行了，有兴趣的自己改成BigInteger吧public static void printNumber2(int maxNum, int id){
List<String> list = new ArrayList<String>();
for(int i =1;i<=maxNum;i++){
list.add(""+i);
}
while(list.size()>2){
int factorial = Test.getfactorial((list.size()-1));
int number = id/factorial;
id = id%factorial;
if(id == 0&&number!=0){
System.out.print(list.get(number-1));
list.remove(number-1);
}else if (id ==0 && number ==0){
System.out.print(list.get(factorial-number));
list.remove(factorial-number);
}else{
System.out.print(list.get(number));
list.remove(number);
}
}
if(id == 1){
System.out.println(list.get(0)+""+list.get(1));
}else{
System.out.println(list.get(1)+""+list.get(0));
}

}

public static int getfactorial(int num){  
int factorial = 1;
for(int i =1 ;i<=num;i++){
factorial *=i;
}
return factorial;
}

Answer 6

我在6楼给的方法有一点小bug，程序里面已经改了
就分三种情况：
如果求余为0，求除不为0，需要移除number前面一位
如果求余为0，求除为0，需要移除number前面一位（这时候前面一位就是-1了，也就是list的最后一位)
如果求余不为0，直接移number

Answer 7

目前测试没发现bug，运行起来也比全排列那个快多了

Answer 8

谁能再给整理下，加上Main的。不然好像不能运行吧
刚学Java好多不懂，谢谢

Answer 9

做好人^_^
Test里面两个方法printNumber 和printNumber2都可以 maxNum就是你要传的N值，id是你要找的第m个。
（因为用的是int，所以N最大只能计算25...不帮你改了嘿嘿）import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Test {
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));

}

public static void printNumber2(int maxNum, int id){
List<String> list = new ArrayList<String>();
for(int i =1;i<=maxNum;i++){
list.add(""+i);
}
while(list.size()>2){
int factorial = Test.getFactorial((list.size()-1));
int number = id/factorial;
id = id%factorial;
if(id == 0&&number!=0){
System.out.print(list.get(number-1));
list.remove(number-1);
}else if (id ==0 && number ==0){
System.out.print(list.get(factorial-number));
list.remove(factorial-number);
}else{
System.out.print(list.get(number));
list.remove(number);
}
}
if(id == 1){
System.out.println(list.get(0)+""+list.get(1));
}else{
System.out.println(list.get(1)+""+list.get(0));
}

}

public static int getFactorial(int num){  
int factorial = 1;
for(int i =1 ;i<=num;i++){
factorial *=i;
}
return factorial;
}

public static void main(String[] args) {
Test.printNumber(7, 29);
Test.printNumber2(7, 29);
}
}

Answer 10

import java.util.*;
public class Test{
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));
        
    }

public static void main(String[] args){
printNumber(3,2);
}
}

借5楼的方法
自己写的主函数