Storing the permutation of a large number in a database

Question

I need to compute and get all the permutations for a large number. Like an array which contains 13 numbers. But though the code I found from the internet worked for 10 values , for 13 numbers it doesn't work as I got an Exception. It says the memory is not enough to show the total permutations. I do not need to print the permutations. For me storing them in the database will be perfectly oki. Still can't I do the calculation if I directly store them in the database. I couldn't find a proper answer for this from internet.

This is the code I used to calculate the permutations.

public class PermutationCalc {

    /**
     * @param args the command line arguments
     */


    static <E> String arrayToString( E[] arr ) {
        final StringBuffer str = new StringBuffer();
        for ( E e : arr ){
            str.append( e.toString() );
        }
        return str.toString();
    }

    static <E> ArrayList<E[]> permutations(E[] arr) {



        final ArrayList<E[]> resultList = new ArrayList<E[]>();
        final int l = arr.length;
        if ( l == 0 ) return resultList;
        if ( l == 1 )
        {
            resultList.add( arr );
            return resultList;
        }

        E[] subClone = Arrays.copyOf( arr, l - 1);
        System.arraycopy( arr, 1, subClone, 0, l - 1 );

        for ( int i = 0; i < l; ++i ){
            E e = arr[i];
            if ( i > 0 ) subClone[i-1] = arr[0];
            final ArrayList<E[]> subPermutations = permutations( subClone );
            for ( E[] sc : subPermutations )
            {
                E[] clone = Arrays.copyOf( arr, l );
                clone[0] = e;
                System.arraycopy( sc, 0, clone, 1, l - 1 );
                resultList.add( clone );
            }
            if ( i > 0 ) subClone[i-1] = e;
        }
        return resultList;
    }

    static ArrayList<String> permutations(String arr) {
        final Character[] c = new Character[arr.length()];
        for ( int i = 0; i < arr.length(); ++i )
            c[i] = arr.charAt( i );

        final ArrayList<Character[]> perms = permutations(c);
        final ArrayList<String> resultList = new ArrayList<String>( perms.size() );

        for ( Character[] p : perms )
        {
            resultList.add( arrayToString( p ) );
        }
        return resultList;
    }

    public static void main(String[] args) {
        //ArrayList<String> str_perms = permutations( "abc" );
        //for ( String p : str_perms ) System.out.println( p );

       ArrayList<Integer[]> int_perms = permutations( new Integer[]{ 1, 2, 3,4,5,6,7,8,9,10} );
       System.gc();
       for ( Integer[] p : int_perms ) System.out.println( arrayToString( p ) );


    }
    }

Can someone please let me know whether I would be able to solve it if I store them in a database and calculate.

PS: Is there another efficient code that I can use in finding 13! of permutation values.

Answer 1

Just to add a few quick thoughts: this seems like one of those problems that calls for cleverness -- what I mean is that for an N digit number, of course there are N! different permutations, but only if we assume that all N digits are unique! Consider the number: 11111 -- there's only 1 permutation! For 11112 there are only 5 permutations, or 5 choose 1 (think about it as there are 5 positions, we choose which of the 5 the two goes in. Rather than just blindly computing all possible permutations, you should first consider how many unique permutations exist.

This smacks of a school assignment, so I'm not going to say more.

Answer 2

It seems in this code you try to get the all permutation first, and then store them to database,

OutOfMemoryError exception occure due to lack of memory to store whole result in the array list,

so try to store result in the database part by part without waiting for whole result, Let's consider 100 permutations at a time.

in the method static <E> ArrayList<E[]> permutations(E[] arr) try this change,

    for ( E[] sc : subPermutations )
        {
            E[] clone = Arrays.copyOf( arr, l );
            clone[0] = e;
            System.arraycopy( sc, 0, clone, 1, l - 1 );
            resultList.add( clone );
            if(resultList.size() == 100) {
                //your code to store current result in the database here.
                resultList.clear(); //clear the ArrayList.
            }
        }
    if(!resultList.isEmpty()) {
       //your code to store current result in the database here.
       resultList.clear(); //clear the ArrayList.
    }

or similar thing to this.

Answer 3

It's silly to actually store all the permutations. Store the data once, and store the permutation number for anything that needs a permutation of the data. Hint: For thirteen items there are 13! permutations. You'd need over 6 gigabytes even if your array items were 1 byte each.

Answer 4

you are getting a OutOfMemoryError exception because you dont have a base case to cut the recursive function. it will just call itself until you get the error. this is about base case

for word permutation

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);//or add to arraylist
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

if numbers

//remember that permutation can have a repeating value or not. size is the size of the number or simply the number itself numberDraw is how many times you need to draw numbers from the pool 

private static void computePermutation(boolean isRepeting, int size,
            int numberDraw) {

        int result = 1;
        int currentsize = size;
        for (int i = 0; i < numberDraw; i++) {
            System.out.println(currentsize);
            result *= currentsize;
            if (!isRepeting) {
                currentsize -= 1;
            }
        }
        System.out.println("premute number: " + result);
    }

ref: recursion permutation

Answer 5

Here's a general solution to getting all permutations of a particular length - in lexicographic order. The question as to whether this data should be pumped into a database must be answered elsewhere.

/**
 * Generates the permutations in lexicographic order.
 */
public class LexicographicPermutationsIterator extends PermutationsIterator implements Iterator<List<Integer>> {

    public LexicographicPermutationsIterator(int length) {
        super(length);
    }

    @Override
    protected boolean nextPerm() {
        boolean got = false;
        // Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
        int k = -1;
        for (int i = 0; i < length - 1; i++) {
            if (indexes.get(i) < indexes.get(i + 1)) {
                k = i;
            }
        }
        if (k >= 0) {
            int ak = indexes.get(k);
            // Find the largest index l such that a[k] < a[l].
            int l = k + 1;
            for (int i = 0; i < length; i++) {
                if (ak < indexes.get(i)) {
                    l = i;
                }
            }
            // Swap the value of a[k] with that of a[l].
            Collections.swap(indexes, k, l);
            // Reverse the sequence from a[k + 1] up to and including the final element a[n].
            Collections.reverse(indexes.subList(k + 1, indexes.size()));
            // We got one.
            got = true;
        }
        return got;
    }

}

/**
 * Iterates over permutations.
 *
 * Actually - it manages a list of Integers that are used as indexes into permutation.
 *
 * The indexes can then be used to permute the objects.
 */
public abstract class PermutationsIterator extends SequenceIterator<List<Integer>> {

    // Length of the lists required.
    protected final int length;
    // The working list.
    protected final List<Integer> indexes;

    public PermutationsIterator(int length) {
        this.length = length;
        // Build my initial indexes as 0..length
        indexes = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            indexes.add(i);
        }
        // Start with the initial position.
        next = Collections.<Integer>unmodifiableList(indexes);
    }

    protected abstract boolean nextPerm();

    @Override
    protected List<Integer> getNext() {
        // Mutate the indexes into the next permutation.
        if (nextPerm()) {
            // That's next!
            return Collections.<Integer>unmodifiableList(indexes);
        }
        return null;
    }

}

/**
 * Implements a sequence as an iterator - leaving a getNext() method for the sequence.
 *
 * @param <T> The type that will be iterated over.
 */
public abstract class SequenceIterator<T> implements Iterator<T> {

    // The next to deliver.
    protected T next = null;

    // Return a new next if one is available.
    protected abstract T getNext();

    @Override
    public boolean hasNext() {
        if (next == null) {
            // Is there one?
            next = getNext();
        }
        return next != null;
    }

    @Override
    public T next() {
        T n = hasNext() ? next : null;
        next = null;
        return n;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Cannot remove from sequence");
    }

}

public void test() {
    try {
        for (int l = 0; l < 5; l++) {
            System.out.println("l = " + l);
            LexicographicPermutationsIterator lit = new LexicographicPermutationsIterator(l);
            while (lit.hasNext()) {
                System.out.println(lit.next());
            }
        }
    } catch (Throwable t) {
        t.printStackTrace(System.err);
    }
}