Wednesday, September 10, 2014

Printing all possible Character Combinations of a String [Combinations][Recursion][Java]

This program prints all possible combinations of a given string and displays them.

Note: If you're thinking that string like "aba" that have two or more repeated characters should have some special care to remove similar combinations, that's incorrect because in combinations every element in the set must be unique. The case referred to above is for permutations. I've a program for that. Check this post: http://coderbots.blogspot.com/2014/09/program-to-find-all-permutations-for.html

Source Code:

/*
 *@author Jatin Thakur coderbots.blogspot.com
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader; 

public class Combinations {

    char a[][];
    
     public void fillArray() throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         System.out.println("Enter the string: ");
         String s= br.readLine(); 
         a = new char[s.length()][2];
         for(int i=0;i<s.length();++i){
             a[i][0] = s.charAt(i);
             a[i][1] = 0; //Unused
         } 
     }

    int totalCombinations = 0; 
    public void combinations(String string, int callingIndex) {
       
        for(int i=callingIndex;i<a.length;++i){
            if(a[i][1] == 1) continue;
            System.out.println(string+a[i][0]);
            totalCombinations++;
            a[i][1] = 1;
            combinations(string+a[i][0], i); 
            a[i][1] = 0;
        }
    }

    public static void main(String[] args) throws IOException {
        Combinations combinations = new Combinations();
        combinations.fillArray(); 
        combinations.combinations("", 0);  
        System.out.println("Total combinations possible: "+combinations.totalCombinations);
    }
}

Output #1:

Enter the string:
123
1
12
123
13
2
23
3
Total combinations possible: 7

Output #2:

Enter the string:
1234
1
12
123
1234
124
13
134
14
2
23
234
24
3
34
4
Total combinations possible: 15

Which is correct.


No comments:

Post a Comment