Rosalind Java|Partial Permutations

Rosalind编程问题之部分排列。

Given: Positive integers n and k such that 100≥n>0 and 10≥k>0
Sample input：

21 7

Return: The total number of partial permutations P(n,k), modulo 1,000,000
Sample output：

51200

题目大意很容易理解：从一个含有n个数字的集合中随机抽取k个数字组成新集合，新集合内元素顺序可变。求得新集合所有的可能数量并取余一百万。

抽象数学模型可知，本题只需要我们计算一个排列数即可完成。
大致思路如下：
1.Scanner获得两个输入数据n和k。
2.order方法判断n和k的大小，并返回响应值。
3.factorial方法计算阶乘。
4.Partfactorial方法计算阶乘差。

public class Partial_Permutations {
    public static void main(String[] args) {
        //1.输入数据
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入总集合个数n：");
        int n = sc.nextInt();

        Scanner sr = new Scanner(System.in);
        System.out.println("请输入待选出元素个数k：");
        int k = sr.nextInt();
        //2.计算n的阶乘即为排列总数，执行子方法1
        order(n, k);

    }

    public static void order(int n, int k) {
        if (n < k) {
            System.out.println("error! n should be more than k");
        } else if (n == k) {
            System.out.println(factorial(n) % 1000000);
        } else {
            System.out.println(Partfactorial(n, k) % 1000000);
        }
    }

    public static long factorial(int n) {
        long sum = 1;
        for (int i = 2; i <= n; i++) {
            sum = sum * i;
        }
        return sum;
    }

    public static long Partfactorial(int n, int k) {
        long sum = 1;
        for (int i = n - k + 1; i <= n; i++) {
            sum = sum * i;
        }
        return sum;
    }
}

可能会有朋友问，计算阶乘能否采用其他算法，例如factorial(n)/factorial(n-k)？。

小编试过，会显示报错，原因如下：
对于Java这种强类型语言，内存溢出是一个很关键的问题。在第二种算法中factorial(n)/factorial(n-k)公式需要我们首先计算n！再计算n-k！。而前者数量级非常大，即使是long变量也会存在溢出的情况。会报错产生负值。采用Partfactorial截断式阶乘计算则能够避免内存溢出，同时极大节省运行内存，加快效率。

此外，本道题中由于事先给定了n和k的范围，使得即使n=k，所计算的阶乘（factorial）也不会超过10！，因此当n=k时，计算n！不存在内存溢出的情况。