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;
    }
}

 

Code in Java for finding Longest Path in Directed Acyclic Graph | Using Topological sorting

Dear Friends,

I am here with you with a problem based on Directed A-cyclic Graph [DAG].

Given a DAG, we are supposed to find the longest path in it.

Friends Please find below the code in java for this problem.

package com.learn.dag.longest.path;

public class LongestPathInDAG {
    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 5, 1);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);
        int s = 1;
        g.findLongestPath(s);
    }

    public static class Graph {
        private int V;
        private int[][] matrix;
        private int[] vertices;
        private boolean[] visited;
        private int[] distances;
        private int[] predecessor;
        private Stack stack;

        public Graph(int V) {
            this.V = V;
            vertices = new int[V];
            visited = new boolean[V];
            predecessor = new int[V];
            distances = new int[V];
            matrix = new int[V][V];
            stack = new Stack(V);
            for (int i = 0; i < V; i++) {
                addVertex(i);
                distances[i] = Integer.MIN_VALUE;
                predecessor[i] = -1;
            }
        }

        private void addVertex(int name) {
            vertices[name] = name;
        }

        public void addEdge(int source, int destination, int weight) {
            matrix[source][destination] = weight;
        }

        public void findLongestPath(int source) {
            invokeTopologicalSort();
            distances[source] = 0; // Initialize source with 0
            updateMaxDistanceForAllAdjVertices(); // for all nodes connected,
                                                    // directly or indirectly,
                                                    // with source will have
                                                    // their distances
                                                    // calculated
            printDistances(source);
            printPath(source);
        }

        private void printDistances(int source) {
            System.out.println("Distances from source " + source + " are as follows: ");
            for (int to = 0; to < V; to++) {
                int distance = distances[to];
                System.out.print("from " + source + " to " + to + ": ");
                if (distance == Integer.MIN_VALUE) {
                    System.out.println(" -Infinity ");
                } else {
                    System.out.println(distance + " ");
                }
            }
            System.out.println();
        }

        private void printPath(int source) {
            System.out.println("Path from source " + source + " to other nodes are as follows: ");
            for (int i = 0; i < V; i++) {
                if (distances[i] == Integer.MIN_VALUE) {
                    System.out.println("No Path from " + source + " to " + i);
                } else if (i != source) {
                    int from = predecessor[i];
                    System.out.print("Path from " + source + " to " + i + ": ");
                    if (from == source) {
                        System.out.print(from + " ");
                    }
                    while (from != source) {
                        System.out.print(from + " ");
                        from = predecessor[from];
                    }
                    System.out.print(i + " ");
                    System.out.println();
                }
            }
        }

        private void updateMaxDistanceForAllAdjVertices() {
            while (!stack.isEmpty()) {
                int from = stack.pop();
                if (distances[from] != Integer.MIN_VALUE) {
                    for (int adjacent = 0; adjacent < V; adjacent++) {
                        if (matrix[from][adjacent] != 0) {
                            if (distances[adjacent] < distances[from] + matrix[from][adjacent]) {
                                predecessor[adjacent] = from;
                                distances[adjacent] = distances[from] + matrix[from][adjacent];
                            }
                        }
                    }
                }
            }
        }

        private void invokeTopologicalSort() {
            for (int i = 0; i < V; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }
        }

        private void dfs(int source) {
            visited[source] = true;
            for (int adjacent = 0; adjacent < V; adjacent++) {
                if (matrix[source][adjacent] != 0 && !visited[adjacent]) {
                    dfs(adjacent);
                }
            }
            stack.push(source);
        }

    }

    public static class Stack {
        private int maxSize;
        private int[] stack;
        private int top = -1;
        private int size = 0;

        public Stack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }

        public void push(int item) {
            stack[++top] = item;
            size++;
        }

        public int pop() {
            int item = stack[top--];
            size--;
            return item;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }
}

Subset Sum problem | Java and Backtracking


Hello Friends,

Today I am here with you with another problem based upon recursion and back tracking.

Suppose we have an array of positive integer elements: 'arr' and a positive number: 'targetSum'.
We need to all the possible subsets of the array elements such that adding the elements of any of the found subsets results in 'targetSum'.

Suppose we have arr= { 2, 3, 4, 5 } and targetSum = 7 then our subsets are {2,5},{3,4}.


Friends I have tried to solve this using Back-tracking, please find the code in java below.

package com.recursion.backtracking;

public class SubSetSum {
    public static void main(String[] args) {
        int[] input = { 2, 3, 4, 5 };
        int targetSum = 7;
        SubSetSum subSetSum = new SubSetSum();
        subSetSum.findSubSets(input, targetSum);
    }

    private int[] set;
    private int[] selectedElements;
    private int targetSum;
    private int numOfElements;

    public void findSubSets(int[] set, int targetSum) {
        this.set = set;
        this.numOfElements = set.length;
        this.targetSum = targetSum;
        selectedElements = new int[numOfElements];
        quicksort(set, 0, numOfElements-1);
        int sumOfAllElements = 0;
        for(int element : set){
            sumOfAllElements += element;
        }
        findSubSets(0, 0, sumOfAllElements);
    }

    private void findSubSets(int sumTillNow, int index, int sumOfRemaining) {
        selectedElements[index] = 1; // selecting element at index : 'index'
        if (targetSum == set[index] + sumTillNow) {
            print();
        }

        // (sum + set[index] + set[index+1] <= targetSum) : this condition
        // ensures selecting
        // the next element is useful and the total sum by including next
        // element will not exceed the target sum.
        if ((index + 1 < numOfElements) && (sumTillNow + set[index] + set[index + 1] <= targetSum)) {
            findSubSets(sumTillNow + set[index], index + 1, sumOfRemaining - set[index]);
        }

        // now exploring the other path: not Selecting the element at index:
        // 'index'
        selectedElements[index] = 0;

        // (sum + set[index+1] <= targetSum) : this condition ensures selecting
        // the next element is useful and the total sum by including next
        // element will not exceed the target sum.

        // (sum + sumOfRemaining - set[index] >= targetSum) ensures the total
        // sum of all the elements by excluding the current element may achieve
        // the target sum, if in case the resultant sum is less than the target
        // sum then exploring this path is of no use
        if ((index + 1 < numOfElements) && (sumTillNow + set[index + 1] <= targetSum)
                && (sumTillNow + sumOfRemaining - set[index] >= targetSum)) {
            findSubSets(sumTillNow, index + 1, sumOfRemaining - set[index]);
        }
    }

    private void print() {
        for (int i = 0; i < numOfElements; i++) {
            if (selectedElements[i] == 1) {
                System.out.print(set[i]+" ");
            }
        }
        System.out.println();
    }

    private void quicksort(int[] arr, int start, int end) {
        if (start < end) {
            swap(arr, (start + (end - start) / 2), end);
            int pIndex = partition(arr, start, end);
            quicksort(arr, start, pIndex - 1);
            quicksort(arr, pIndex + 1, end);
        }
    }

    private int partition(int[] arr, int start, int end) {
        int pIndex = start, pivot = arr[end];
        for (int i = start; i < end; i++) {
            if (arr[i] < pivot) {
                swap(arr,pIndex,i);
                pIndex++;
            }
        }
        swap(arr,pIndex,end);
        return pIndex;
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}



Sunday 30 August 2015

Make correct equation to achieve a given RHS. | Java and Backtracking

Hello Friends,

I am with you with another problem based upon back tracking.

If we have an integer array A[] and another integer value K, we need to find is there a sequence of  '+', '-' exists  such that if applied on the elements of A produce K. The operations need to be applied without changing the relative position of the array elements.

Friends I have used recursion with back tracking to solve this problem, please find the code below for the same.
package com.recursion.backtracking;

import java.util.Arrays;

public class MakeValidEquation {
    public static void main(String[] args) {
        int numbers[] = { 2, 3, 4, 5 };
        int RHS = 6;
        
        MakeValidEquation equation = new MakeValidEquation(numbers, RHS);
        boolean isRHSAchievable = equation.makeValidEquation(0, numbers.length);
        if(isRHSAchievable){
            System.out.println("Operations : "+Arrays.toString(equation.operators));
        }else{
            System.out.println("RHS can not be achieved by +, - on the numbers");
        }
    }

    public MakeValidEquation(int[] numbers, int RHS) {
        this.numbers = numbers;
        int n = numbers.length;
        this.RHS = RHS;
        operators = new char[n-1];
    }

    private char[] operators;
    private int[] numbers;
    private int RHS;

    public boolean makeValidEquation(int i, int n) {
        if (i == n - 1) {
            int result = numbers[0];
            for (int j = 0; j <= n - 2; j++) {
                if (operators[j] == '+') {
                    result = result + numbers[j + 1];
                } else if (operators[j] == '-') {
                    result = result - numbers[j + 1];
                }
            }
            return result == RHS;
        }
        operators[i] = '+';
        if(makeValidEquation(i+1, n)){
            return true;
        }else {
            // try next option
            operators[i] = '-';
            if(makeValidEquation(i+1, n)){
                return true;
            }
            else return false;
        }
    }
}



Solution in java for : Finding if a path exists from start to end cell in a maze | Back Tracking and Dynamic Programming

Hello Friends,

Today I am here with you with a recursion problem. Today we have a little tough problem.

Suppose we have a maze and we need to determine if a path exits from starting point  to the last point in the maze. Maze is represented by a 2-d-matrix. Lets call this matrix 'maze'. maze[0][0] represents the starting point and maze[rows-1][columns-1] be the end point. Any cell 'maze[i][j]' can be used as a part of the path if it contains 1 and can be reached from immediate top, left, right or bottom cells. Cells containing 0 are the ones which can not be used in the path.

Friends I have tried solving this using two Approaches.
    1. Recursion [Back Tracking] : Depth search First approach : DFS
    2. Dynamic Programming.

**Note that Dynamic programming approach will fail for few examples where path exists by traversing upwards or left side like below example

1 1 1 1 0 0 0 0
0 0 0 1 0 1 1 1
0 1 1 1 0 1 0 1
0 1 0 0 0 1 0 1
0 1 1 1 1 1 0 1


Friends please find below the code for this problem.
package com.recursion.backtracking;

public class Maze {
    public static void main(String[] args) {
        int mazeForDFS[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        int mazeForDP[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        boolean isPathAvailableDFS = isPathAvailable(mazeForDFS, 0, 0, mazeForDFS.length, mazeForDFS[0].length);
        boolean isPathAvailableDP = isPathAvailable(mazeForDP);
        System.out.println("DFS way : " + isPathAvailableDFS);
        System.out.println("DP  way : " + isPathAvailableDP);
    }

    public static final int VISITED = 0;

    /**
     * This is a recursive approach based upon recursion and Back tracking. If a
     * end point is reached then true is returned all the way up to the first
     * calling of the method, else false is returned. False is propagated  down
     * the call stack if all the options [top, left, right, down] are explored
     * and no other cell is left to explore.
     * 
     * @param maze
     * @param i
     * @param j
     * @param rows
     * @param columns
     * @return true if path exists else returns false;
     */
    public static boolean isPathAvailable(int[][] maze, int i, int j, int rows, int columns) {
        if (i == rows - 1 && j == columns - 1) {
            return true;
        }
        maze[i][j] = VISITED;
        if (j + 1 < columns && maze[i][j + 1] != VISITED) {
            if (isPathAvailable(maze, i, j + 1, rows, columns)) {
                return true;
            }
        }
        if (i + 1 < rows && maze[i + 1][j] != VISITED) {
            if (isPathAvailable(maze, i + 1, j, rows, columns)) {
                return true;
            }
        }
        if (j - 1 >= 0 && maze[i][j - 1] != VISITED) {
            if (isPathAvailable(maze, i, j - 1, rows, columns)) {
                return true;
            }
        }
        if (i - 1 >= 0 && maze[i - 1][j] != VISITED) {
            if (isPathAvailable(maze, i - 1, j, rows, columns)) {
                return true;
            }
        }
        return false;
    }

    /**
     * This method uses Dynamic programming to solve the problem. It exploits
     * the information for all the first row and column information and then
     * verifies the rest of the cells if they are reachable. In case they are
     * not reachable this method marks them as 0, as they are as good as cells
     * with value = 0;
     * 
     */
    public static boolean isPathAvailable(int[][] maze) {
        int rows = maze.length;
        int coloumns = maze[0].length;
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < coloumns; j++) {
                if (maze[i][j] == 1 && maze[i - 1][j] == 0 && maze[i][j - 1] == 0) {
                    maze[i][j] = 0;
                }
            }
        }
        return maze[rows - 1][coloumns - 1] == 1;
    }
}