Java permutations

Question

I am trying to run my code so it prints cyclic permutations, though I can only get it to do the first one at the moment. It runs correctly up to the point which I have marked but I can't see what is going wrong. I think it has no break in the while loop, but I'm not sure. Really could do with some help here.

package permutation;

public class Permutation {
static int DEFAULT = 100;

public static void main(String[] args) {
    int n = DEFAULT;
    if (args.length > 0)
        n = Integer.parseInt(args[0]);

    int[] OA = new int[n];
    for (int i = 0; i < n; i++)
        OA[i] = i + 1;

    System.out.println("The original array is:");
    for (int i = 0; i < OA.length; i++)
        System.out.print(OA[i] + " ");
    System.out.println();

    System.out.println("A permutation of the original array is:");
    OA = generateRandomPermutation(n);
    printArray(OA);
    printPemutation(OA);
}

static int[] generateRandomPermutation(int n)// (a)
{
    int[] A = new int[n];
    for (int i = 0; i < n; i++)
        A[i] = i + 1;

    for (int i = 0; i < n; i++) {
        int r = (int) (Math.random() * (n));
        int swap = A[r];
        A[r] = A[i];
        A[i] = swap;
    }
    return A;
}

static void printArray(int A[]) {
    for (int i = 0; i < A.length; i++)
        System.out.print(A[i] + " ");
    System.out.println();
}

static void printPemutation(int p[])// (b)
{
    System.out
            .println("The permutation is represented by the cyclic notation:");
    int[] B = new int[p.length];
    int m = 0;
    while (m < p.length)// this is the point at which my code screws up
    {
        if (!check(B, m)) {
            B = parenthesis(p, m);
            printParenthesis(B);
            m++;
        } else
            m++;
    }// if not there are then repeat
}

static int[] parenthesis(int p[], int i) {
    int[] B = new int[p.length];
    for (int a = p[i], j = 0; a != B[0]; a = p[a - 1], j++) {
        B[j] = a;
    }
    return B;
}

static void printParenthesis(int B[]) {
    System.out.print("( ");
    for (int i = 0; i < B.length && B[i] != 0; i++)
        System.out.print(B[i] + " ");
    System.out.print(")");
}

static boolean check(int B[], int m) {
    int i = 0;
    boolean a = false;
    while (i < B.length || !a) {
        if ((ispresent(m, B, i))){
            a = true;
            break;
        }
        else
            i++;
    }
    return a;
}

static boolean ispresent(int m, int B[], int i) {
    return m == B[i] && m < B.length;
}
}

Do us all a favour and run your code through an automatic indenter. You have nested ifs and such at the exact same level of indentation, which makes it unnecessarily difficult to decipher the logic. — Anon.
– Anon., Commented Dec 2, 2010 at 23:01

morja · Accepted Answer · 2010-12-03 00:44:20Z

2

Among others you should check p[m] in check(B, p[m]) instead of m:

in static void printPemutation(int p[]):

while (m < p.length){
    if (!check(B, p[m])) {
         B = parenthesis(p, m);
         printParenthesis(B);
    }
    m++;
}

then

static boolean check(int B[], int m) {
    int i = 0;
    while (i < B.length) {
        if (m == B[i]) {
            return true;
        }
        i++;
    }
    return false;
}

this does somehow more what you want, but not always i fear...

edited Dec 3, 2010 at 0:44

answered Dec 2, 2010 at 23:24

morja

8,5703 gold badges43 silver badges62 bronze badges

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

9 Comments

user528676 Over a year ago

I just want it to shift to the next cyclic permutation say for 51432 represented as (521)(43). At the moment however it is only printing (521). The check method runs through (521) and sees what the first number not in it is and then starts printing the second bracket, or that is the idea anyway. However I'm at a dead end with ideas on how to get it to shift to start printing the next bracket.

user528676 Over a year ago

Implementing you tip I now get

user528676 Over a year ago

The original array is: 1 2 3 4 A permutation of the original array is: 2 3 1 4 The permutation is represented by the cyclic notation: ( 2 3 1 )( 2 3 1 )( 3 1 2 )( 1 2 3 )( 4 )

morja Over a year ago

Sorry, I can not fully fix your code. I think you have some errors in the permutation function too. Maybe you should first try to create valid permutations for one class: en.wikipedia.org/wiki/Cycle_notation e.g. (1 2),(1 3),(1 4),(2 3),(2 4),(3 4)

user528676 Over a year ago

Trying to debug It seems to think the error is in the third from last line. In the ispresent method. Any other ideas for how to scan the printed cycle to find the next step or am I thinking about this the wrong way?

|

Collectives™ on Stack Overflow

Java permutations

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related