Java permutations 2

Question

I asked a question on helping me with this question about a week ago

Java permutations

, with a problem in the print permutation method. I have tidied up my code and have a working example that now works although if 5 is in the 5th position in the array it doesn't print it. Any help would be really appreciated.

 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);
    printPermutation(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 printPermutation(int[] p)

{
    int n = p.length-1;
    int j = 0;
    int m;
    int f = 0;

    System.out.print("(");
    while (f < n) {
        m = p[j];
        if (m == 0) {
            do
                f++;
            while (p[f] == 0 && f < n);
            j = f;
            if (f != n)
                System.out.print(")(");
        } 
        else {
            System.out.print(" " + m);
            p[j] = 0;
            j = m - 1;
        }
    }
    System.out.print(" )");
}
}

Tony Ennis · Accepted Answer · 2010-12-05 22:41:05Z

0

I'm not too crazy about

int n = p.length-1;

followed by

while (f < n) {

So if p is 5 units long, and f starts at 0, then the loop will be from 0 to 3. That would seem to exclude the last element in the array.

answered Dec 5, 2010 at 22:41

Tony Ennis

12.4k8 gold badges59 silver badges79 bronze badges

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

10 Comments

user528676 Over a year ago

If I change it to int n = p.length it gives back an error though. This is my problem, that it doesn't read until the last element, and though trying to follow where the error is I can't find it.

Tony Ennis Over a year ago

Fair enough. Have you stepped through the routine with a debugger to see where things go awry? What error is being given?

user528676 Over a year ago

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5 at permutation.Permutation.printPermutation(Permutation.java:58) at permutation.Permutation.main(Permutation.java:21)

user528676 Over a year ago

So its basically running out of the length of the array. Though in that case it does print the 5 if its in the 5th position though not the last bracket, changing the length gets rid of the error but also the last number.

Karl Knechtel Over a year ago

Why don't you just print the permutation the same way you print the original array? The permutation is being held in the exact same sort of array.

|

Liviu T. · Accepted Answer · 2010-12-05 22:47:07Z

0

You can use the shuffle method of the Collections class

Integer[] arr = new Integer[] { 1, 2, 3, 4, 5 };
List<Integer> arrList = Arrays.asList(arr);
Collections.shuffle(arrList);
System.out.println(arrList);

answered Dec 5, 2010 at 22:47

Liviu T.

23.7k10 gold badges64 silver badges59 bronze badges

1 Comment

user528676 Over a year ago

Its homework and I have to use imperative(?) methods although though that would be a lot simpler.

dspyz · Accepted Answer · 2010-12-06 01:17:41Z

0

I don't think swapping each element with a random other element will give a uniform distribution of permutations. Better to select uniformly from the remaining values:

Random rand = new Random();
ArrayList<Integer> remainingValues = new ArrayList<Integer>(n);
for(int i = 0; i < n; i++)
    remainingValues.add(i);
for(int i = 0; i < n; i++) {
    int next = rand.nextInt(remainingValues.size());
    result[i] = remainingValues.remove(next);
}

Note that if order of running-time is a concern, using an ArrayList in this capacity is n-squared time. There are data-structures which could handle this task in n log n time but they are very non-trivial.

answered Dec 6, 2010 at 1:17

dspyz

5,6042 gold badges31 silver badges71 bronze badges

Comments

JerryK · Accepted Answer · 2010-12-06 07:09:38Z

0

This does not answer the problem you have identified.

Rather i think it identifies a mistake with your generateRandomPermutation(int n) proc.

If you add a print out of the random numbers generated (as i did below) and run the proc a few times it allows us to check if all the elements in the ARRAY TO BE permed are being randomly selected.

static int[] generateRandomPermutation(int n)
{
    int[] A = new int[n];
    for (int i = 0; i < n; i++)
        A[i] = i + 1;
     System.out.println("random nums generated are: ");
    for (int i = 0; i < n; i++) {
        int r = (int) (Math.random() * (n));
         System.out.print(r + " ");

Run the proc several times. Do you see what i see?

Jerry.

edited Dec 6, 2010 at 7:09

answered Dec 6, 2010 at 6:49

JerryK

821 silver badge8 bronze badges

Collectives™ on Stack Overflow

Java permutations 2