5 replies to this topic

[brightmatter]

I have found some code for this when dealing with a string but it uses a print as you go recursive method instead of capturing all the data and returning in after completion.
Permutations.java
I thought I might like to do this but does anyone know of a more efficient way to do this?

    private Object[][] resulting2DArray;

    public static void perm2(Object[] s) {

       int N = s.length;

       resulting2DArray = new Object[N][N];

       Object[] a = new Object[N];

       for (int i = 0; i < N; i++)

           a[i] = s[i];

       perm2(a, N);

       return resulting2DArray;

    }


    private static void perm2(Object[] a, int n) {

        if (n == 1) {

           //some how dump the contents into the 2D array "resulting2DArray"

            return;

        }

        for (int i = 0; i < n; i++) {

            swap(a, i, n-1);

            perm2(a, n-1);

            swap(a, i, n-1);

        }

    }  


    // swap the characters at indices i and j

    private static void swap(Object[] a, int i, int j) {

        Object c;

        c = a[i]; a[i] = a[j]; a[j] = c;

    }

Does anyone have a brilliant idea?

[win4t4]

Hi,

What do you mean by efficient ?
If that means, a method which big-O complexity is smaller than you snippet code. I think there isn't.
But if you mean a method which is easier to understand (because you wanted to get all the permutation). Yes I think I have an answer :)

Winata

[WingedPanther]

This is an extraordinarily bad idea. You're dealing with O(n!) space complexity, which is a fantastic way to chew up all available RAM as soon as you get a slightly long sequence.

[fayyazlodhi]

Following might be a very useful one

http://forum.codecal...rmutations.html

[Ritwik I the programmer]

Yoy have used excess space for 2-D Array. You have to have a member variable counter to tackle that. On completion of individual permutations, yo just have to use a for loop to copy individual Object objects into the row indicated by the counter. Increment the counter first, and then use it as the row index. The loop counter should do for collumn counter in both the 1-D and 2-D array

[Ritwik I the programmer]

P.S.Do not go for N >= 7, things can get real bad