Search This Blog

Thursday, 11 August 2016

Generating permutations in Java using array

The following code generates all possible permutations till the entered integer integers. Similar program can be made to permute the characters of a string.

Explanation:
First we enter only 1 in a array.
Then for entering 2 we have two choices- before 1 and after 1 as- "21" and "12".
The program uses recursion so for "21" we can add 3 at 3 different places as "321", "231" and "213" i.e., at first position, between them and in the last position.

The code is given below: 

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author Aditya Vijayvergia @ thecodingedge.blogspot.com
 */
public class GeneratingPermutations {

    static int perm(int []a,int n,int m)
    {                          //n=the element that is being added in this recursive call
        int []b=new int[m];    //m=total no of elemets
        for(int i=0;i<n;i++)
            {
                System.arraycopy(a, 0, b, 0, m);//copy the state of array a to array b
                for(int j=n-1;j>i;j--)//shift values 1 step ahead
                    b[j]=b[j-1];
                b[i]=n;//store n at the empty location
                if(n==m)
                {
                    System.out.println(Arrays.toString(b));
                }
                else{    
                    perm(b,n+1,m);   
                    }
            }
        return 0;
    }
    
    public static void main(String[] args) {
        int m;
        System.out.print("enter the number of elements:");
        Scanner in=new Scanner(System.in);
        m=in.nextInt();
        int []a=new int[m];
        perm(a,1,m);
    }
}

Sample Output:

No comments:

Post a Comment