CODEWITHSUNDEEP
javapermutation
Joe24
Joe24

Reputation: 161

How to use Permutation Generator Java

I have been given this permutation generator that I have shown below. I have initialized it like this: PermutationGenerator perm = new PermutationGenerator(4);.

I am trying to use the next() function multiple times but I keep getting the same results. How do I use this code properly to generate permutations? 

int[] try = p.next()

for(int i=0;i<try.length;i++) {
    System.out.println(try[i]);
}

// Generator of all permutations of: 0,1,2,...,n-1

public class PermutationGenerator {
// private data

private int[] perm;
private boolean first;

// constructor

public PermutationGenerator (int n) {
    perm = new int [n];
    first = true;
}


// return the next permutation, or null if no more
// Reference: Wikipedia Permutation 5.2.2

public int[] next () {
    int n = perm.length;

    // starting permutation: 0 1 2 3 ... n-1

    if (first) {
        first = false;
        for (int i = 0 ; i < n ; i++)
            perm [i] = i;
        return perm;
    }

    // construct the next permutation
    // find largest k so that perm[k] < perm[k+1]; if none, finish

    int i, j, k, l;

    for (k = n - 2 ; k >= 0 && perm [k] >= perm [k + 1] ; k--)
        ;
    if (k < 0)
        return null; // no more

    // find largest l so that perm[k] < perm[l]

    for (l = n - 1 ; l >= 0 && perm [k] >= perm [l] ; l--)
        ;

    // swap perm[k] and perm[l]

    swap (perm, k, l);

    // reverse perm[k+1]...perm[n-1]

    for (i = k + 1, j = n - 1 ; i < j ; i++, j--)
        swap (perm, i, j);

    return perm;
}


// swap a[i] and a[j]

private static void swap (int a[], int i, int j) {
    int temp = a [i];
    a [i] = a [j];
    a [j] = temp;
}
}

Upvotes: 1

Views: 3844

Answers (1)

Terry Li
Terry Li

Reputation: 17268

import java.util.Random;

public class PermutationGenerator {

    private int[] perm;
    private static Random r = new Random();

    public PermutationGenerator(int n) {
        perm = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = i;
        }
    }

    public int[] next() {
        helper(perm, perm.length);
        return perm;
    }

    private static void helper(int[] a, int length) {
        if (length > 1) {
            swap(a, r.nextInt(length), length - 1);
            helper(a, length - 1);
        }
    }

    private static void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        PermutationGenerator generator = new PermutationGenerator(4);
        int[] perm = generator.next();
        for (int i = 0; i < perm.length; i++) {
            System.out.println(perm[i]);
        }
    }
}

I just took five minutes from my lunch break and wrote the working code above. Try it if you'd like to.

As for your posted code, it is not very readable and I didn't look into it much. But an immediate and obvious error I've found inside the next method is that it used comparisons as in perm [k] >= perm [k + 1] and perm [k] >= perm [l].

When generating permutations, it is absolutely unnecessary and even wrong to do any comparisons among elements.

Upvotes: 1

Related Questions