Sunday, September 7, 2014

Program to find all the Permutations for a given String (without Repetitions due to similar characters) [Permutations][Java]

This program finds all the Permutations for a given String.

For strings like 121 , having repetitions, the results don't include the repeated permutations (112, 112 for example) appears only once.

Source:

/**
 *
 * @author Jatin Thakur
 */

import java.io.*;
import java.util.*;

public class PermutationsString {

    StringBuffer sb = new StringBuffer(); 
    String prevString, nextString;

    public void permuteReducedMemory(char[][] array, StringBuffer parsed) {
        int flag = 1;
        for (int i = 0; i < array.length; ++i) {
            if (array[i][1] == 0) {
                flag = 0;
            }
        }

        if (flag == 1) { 
                System.out.println(parsed.toString());
                return;  
        }

        for (int i = 0; i < array.length; ++i) {
            if (array[i][1] == 1) {
                continue;
            }
            int flagger = 0;
            prevString = parsed.toString()+array[i][0]; 
            for (int j = i + 1; j < array.length; ++j) {
                if (array[j][1] == 1) {
                    continue;
                }
                nextString = parsed.toString()+array[j][0];
                if (prevString.matches(nextString)) {
                    System.out.println("Avoided a duplicate");
                    flagger = 1;
                    break;
                } 
            }
            if(flagger == 1){
                continue;
            }
            parsed.append(array[i][0]);
            array[i][1] = 1;
            permuteReducedMemory(array, parsed);
            array[i][1] = 0;
            sb.deleteCharAt(parsed.length() - 1);
        }
    }

    public static void main(String[] args) {
        PermutationsString permut = new PermutationsString();

        System.out.println("Enter the string : ");
        List<Character> chars = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String string = null;
        try {
            string = br.readLine();
            System.out.println();
        } catch (IOException e) {
            System.out.println("Error reading input");
            System.exit(0);
        }

        char array[][] = new char[string.length()][2];
        for (int i = 0; i < string.length(); ++i) {
            array[i][0] = string.charAt(i);
        }
        permut.permuteReducedMemory(array, permut.sb);
    }
}

Output #1:

Enter the string :
121

211
112
121

Output #2:

Enter the string :
abcd

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba


No comments:

Post a Comment