Permutation problem

Question

I have posted a similar problem in Permutation of array, but I want the following.

We know that with length n there are n! possible permutations from which one such that all element are in order. They are in sorted variant so I want break permutation when the array is ordered and print result, but something is wrong. I think that problem is repeated of permutation.

Here is my code

import java.util.*;

public class permut{

    public static Random r=new Random();

    public static void display(int a[],int n) {
        for (int i=0;i<n;i++) {
            System.out.println(a[i]);
        }
    }

    public static void Permut(int a[],int n) {
        int j=0;
        int k=0;
        while (j<fact(n)) {
            int   s=r.nextInt(n);
            for (int i=0;i<n;i++){
                k=a[i];
                a[i]=a[s];
                a[s]=k;
            }

            j++;
            if (sorted(a,n))
                display(a,n);
            break;
        }
    }

    public static void main(String[]args) {
        int a[]=new int[]{3,4,1,2};
        int n=a.length;
        Permut(a,n);
    }

    public static int fact(int n) {
        if (n==0 || (n==1)  )
            return 1;
        return n*fact(n-1);
    }

    public static boolean sorted(int a[],int n  ) {
        boolean  flag=false;
        for (int i=0;i<n-1;i++) {
            if (a[i]<a[i+1]) {
                flag=true;
            }
            else {
                flag=false;
            }
        }
        return flag;
    }
}

The result is nothing. How can this problem be fixed?

Answer 1

Are you trying to go over all the permutations systematically, or just try them randomly? A random swapping of elements in the array does not ensure that you actually go over all the possibilities, and in fact there's very little chance that you will cover even most of them after n! tries. If you want to go over all the possibilities you need a systematic approach, such as using recursion or iteration. In each step you insert 1 element into the array (which isn't already in the array) and then try all the possibilities for the remaining part of the array. Also, be aware that n! is a very large number, even for a moderately-sized n. So this algorithm is very inefficient, and might take more time than you would like it, even for n in the area of 15.

Answer 2

This is how to systematically permute a string:

Class-Definition/RecursivemethodtofindallpermutationsofaString.htm">http://www.java2s.com/Tutorial/Java/0100_Class-Definition/RecursivemethodtofindallpermutationsofaString.htm

Should be adaptable for permuting an array.

In your sorted() method you might consider adding "break;" in the else clause and having "<=" in the if above it.