Monday, 31 August 2015

Finding permutations of r elements from total of n elements. | Code in Java

Dear Friends,

I am here with you with another problem based on permutations and combinations.

We need to find all the permutations of R elements out of total N objects. For this we will first find  the combinations of R elements out of N elements and will permute them.

Please find below the code in java for this.
package com.learn.permutation;

import java.util.Arrays;

public class PermutationOfRelementsFromNElements {
    public static void main(String[] args) {
        char[] A = { 'P', 'Q', 'R', 'S' };
        int n = A.length;
        int r = 2;
        char[] T = new char[r];
        combine(A, T, n, r);
    }

    /**
     * To get permutations of r elements from total N eleemnts first we take r
     * combinations from n elements and for each combination we permute the r
     * elements
     * 
     * @param A
     * @param T
     * @param n
     * @param r
     */
    public static void combine(char[] A, char[] T, int n, int r) {
        if (r == 0) {
            permute(T, 0);
        } else if (n >= r) {
            T[r - 1] = A[n - 1];
            combine(A, T, n - 1, r - 1);
            combine(A, T, n - 1, r);
        }
    }

    /**
     * This method permutes the r elements in array T, T is prepared from the
     * combine method. T[] contains the combinations of r elements from N
     * elements
     * 
     * @param T
     * @param swapingPosition
     */
    public static void permute(char[] T, int swapingPosition) {
        if (swapingPosition == T.length) {
            System.out.println(Arrays.toString(T));
        } else {
            for (int i = swapingPosition; i < T.length; i++) {
                swap(T, swapingPosition, i);
                permute(T, swapingPosition + 1);
                swap(T, swapingPosition, i);
            }
        }
    }

    /**
     * This is simple utility method to swap two elements of the array A at
     * given two indices, index1 and index2
     * 
     * @param A
     * @param index1
     * @param index2
     */
    public static void swap(char[] A, int index1, int index2) {
        char temp = A[index1];
        A[index1] = A[index2];
        A[index2] = temp;
    }
}