Strange Error in java permutation generating algorithm

Question

My algorithm generates permutations of the number 0...n, where n can be any number from 1 to 9. it works perfectly for numbers from 1 to 8. But when I run it with 9, it runs for a while. Then suddenly aborts the process and exits... with no error message or any such thing! I have been coding in java for quite a while and have never experienced this error.

My algorithm:-

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

}

Without the print statement, this runs pretty fast for numbers till 8 (for 8 it runs under 280ms). But for 9 it just stops suddenly after printing the last permutation. Can someone please help? Thank you!

Looks like it's a SIGSEGV: ideone.com/DeDNF7. I guess more than 3 million Longs takes up too much memory? See ideone.com/67764E — irrelephant
– irrelephant, Commented Dec 26, 2012 at 11:02

Peter Lawrey · Accepted Answer · 2012-12-26 11:48:57Z

1

I suspect you have a resource limited JVM and you are getting very close to the limit in the amount of memory you have. Try running without printing but with -verbosegc Creating a List<Long> is going to consume allot of memory which is only fine if you have plenty of free memory.

BTW I wouldn't print positive numbers with a - in front of them as they can look like negative numbers. If I run on my machine, I see (without -)

Size: 3628800
Time: 18645

without printing

Size: 3628800
Time: 1420

with -mx128m

Size: 3628800
Time: 1894

with -mx100m it takes a very long time, to throw

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)

You are going to need at least a heap size of 128 MB to run this efficiently.

edited Dec 26, 2012 at 11:48

answered Dec 26, 2012 at 11:33

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Peter Lawrey Over a year ago

An alternative is to use TLongArrayList which wraps a long[] but given you can buy 32 GB for about $200, I would just use more memory.

MrLore · Accepted Answer · 2012-12-26 11:30:35Z

The problem isn't with your code, it's with System.out, it can't display the amount of data you're giving it in a reasonable amount of time so it throws a hissy-fit. When I tried to run your application, it was still going after 6 minutes so I cancelled it, commented out the print statement, and ran it again, which took 2 seconds (according to my compiler) to output:

Size:-3628800
Time:-962

So I changed your code to instead print the data to a file, and ran it again, and it took 4 seconds to execute and created a nice 83.1 MB text file of the output. Here's the code I used (I'd change it to use less static things though):

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

On my laptop the problem still persists even if i run it without printing output.

Collectives™ on Stack Overflow

Strange Error in java permutation generating algorithm

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related