0

我的算法生成数字 0...n 的排列，其中 n 可以是 1 到 9 之间的任何数字。它适用于从 1 到 8 的数字。但是当我使用 9 运行它时，它会运行一段时间。然后突然中止进程并退出......没有错误消息或任何类似的东西！我在java中编码已经有一段时间了，从来没有遇到过这个错误。

我的算法：-

package utils;

import java.util.ArrayList;

class Lexicography {

    static ArrayList<Long> perms = new ArrayList<Long>();

    public static void main(String[] args){
        long time = System.currentTimeMillis();
        getPermutations(Integer.valueOf(args[0]));

        System.out.println("\nSize:-"+perms.size()+"\nTime:-"+(System.currentTimeMillis()-time));
        //This println is never printed... java aborts before that
    }

    public static ArrayList<Long> getPermutations(int num){
        int[] n = new int[num+1];
        for(int i=0; i<=num; i++) n[i]=i;
        perms.add(getLong(n));
        for(int i=num; i>=0; i--) permutate(n[i],n);
        return perms;
    }

    private static void permutate(int k, int[] n){
        if(k>n.length) return;
        int p=0;
        for(int i:n){ if(i==k) break; p++;}

        for(int i=0; i<n.length; i++){
            if(i==p || n[i]<k) continue;
            n=swap(p,i,n);
            perms.add(getLong(n));
            System.out.println("i:"+(i+1)+" k:"+k+"    n:"+getLong(n));//this prints all permutations till the last one and then poof!

            for(int j=k-1; j>=0; j--) permutate(j,n);
            n=swap(p,i,n);
        }
    }

    private static int[] swap(int i, int f, int[] a){
        int t=a[f];
        a[f]=a[i]; a[i]=t;
        return a;
    }

    private static long getLong(int[] n){
        long ten=1, num=0;
        for(int i=n.length-1; i>=0; i--){
            num+=n[i]*ten; ten*=10;
        }
        return num;
    }

}

如果没有 print 语句，直到 8 的数字运行得非常快（对于 8，它运行在 280 毫秒以下）。但是对于 9，它在打印最后一个排列后突然停止。有人可以帮忙吗？谢谢！

4

2 回答 2

1

问题不在于您的代码，而在于System.out，它无法在合理的时间内显示您提供给它的数据量，因此它会引发混乱。当我尝试运行您的应用程序时，它仍然在 6 分钟后运行，所以我取消了它，注释掉了 print 语句，然后再次运行它，这需要 2 秒（根据我的编译器）输出：

Size:-3628800
Time:-962

因此，我更改了您的代码，改为将数据打印到文件中，然后再次运行，执行时间为 4 秒，并创建了一个漂亮的 83.1 MB 输出文本文件。这是我使用的代码（我会更改它以使用更少的静态内容）：

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

class Lexicography
{
    static ArrayList<Long> perms = new ArrayList<>();
    private static BufferedWriter out;

    public static void main(String[] args) throws IOException
    {
        File outputFile = new File("output.txt");
        if(!outputFile.exists())
        {
            outputFile.createNewFile();
        }
        out = new BufferedWriter(new FileWriter(outputFile.getAbsolutePath()));
        long time = System.currentTimeMillis();
        getPermutations(Integer.valueOf("9"));
        System.out.println("\nSize:-" + perms.size() + "\nTime:-" + (System.currentTimeMillis() - time));
        out.close();
    }

    public static ArrayList<Long> getPermutations(int num) throws IOException
    {
        int[] n = new int[num + 1];
        for(int i = 0; i <= num; i++)
        {
            n[i] = i;
        }
        perms.add(getLong(n));
        for(int i = num; i >= 0; i--)
        {
            permutate(n[i], n);
        }
        return perms;
    }

    private static void permutate(int k, int[] n) throws IOException
    {
        if(k > n.length)
        {
            return;
        }
        int p = 0;
        for(int i : n)
        {
            if(i == k)
            {
                break;
            }
            p++;
        }

        for(int i = 0; i < n.length; i++)
        {
            if(i == p || n[i] < k)
            {
                continue;
            }
            n = swap(p, i, n);
            perms.add(getLong(n));
            out.write("i:" + (i + 1) + " k:" + k + "    n:" + getLong(n) + "\n");
            for(int j = k - 1; j >= 0; j--)
            {
                permutate(j, n);
            }
            n = swap(p, i, n);
        }
    }

    private static int[] swap(int i, int f, int[] a)
    {
        int t = a[f];
        a[f] = a[i];
        a[i] = t;
        return a;
    }

    private static long getLong(int[] n)
    {
        long ten = 1, num = 0;
        for(int i = n.length - 1; i >= 0; i--)
        {
            num += n[i] * ten;
            ten *= 10;
        }
        return num;
    }
}
于 2012-12-26T11:22:24.903 回答
1

我怀疑您的 JVM 资源有限，并且您的内存量已接近极限。尝试在不打印的情况下运行，但使用-verbosegc 创建 aList<Long>会消耗分配的内存，这只有在您有足够的可用内存时才可以。

顺便说一句，我不会-在它们前面打印正数，因为它们看起来像负数。如果我在我的机器上运行，我会看到（不带-）

Size: 3628800
Time: 18645

无需打印

Size: 3628800
Time: 1420

和-mx128m

Size: 3628800
Time: 1894

需要-mx100m很长时间才能抛出

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at java.lang.Long.valueOf(Long.java:577)
at Lexicography.permutate(Lexicography.java:31)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.getPermutations(Lexicography.java:19)
at Lexicography.main(Lexicography.java:9)

您将需要至少 128 MB 的堆大小才能有效地运行它。

于 2012-12-26T11:33:04.177 回答