Make delicious recipes!

Print all combinations of a string
(assume that duplicates are allowed)



If there are 'n' elements and we have to choose 'r' from them (assuming each element's quantity is unlimited),
then each element can be chosen in 'n' ways, so 'r' elements can be chosen in nxnx ... n = nr times.
Java code:
public class CombinationNonRecursive
{
    static int count=0;
    public static void main(String[] args)
    {
        char[] values = {'a', 'b', 'c', 'd', 'e'};
        int n = values.length;
        int r = 3;
        int output[] = new int[r];

        for(int numIterations=0; numIterations<Math.pow(n,r); numIterations++)
        {
            print(values, r, output);
            int index = 0;
            while(index < r)
            {
                if(output[index] < n-1)
                {
                    output[index]++;
                    break;
                }
                else
                {
                    output[index]=0;
                }
                index++;
            }
        }
    }

    private static void print(char[] values, int r, int[] output)
    {
        System.out.print(String.format("\n%2d", ++count) + ") ");
        while(r-- > 0)
        {
            System.out.print(values[output[r]]);
        }
    }
}

We could have also used recursion to achieve the same thing.
An index would be incremented in each recursive call and recursion would terminate when the index became >= r
And in every recursive call, we would iterate from 0 to n to choose a character for the indexth position.

You might be tempted to do this using two loops - one running from 0 to r and the other from 0 to n
However, that will generate only rxn combinations and would be incorrect.

Sample Run:
 1) aaa
 2) aab
 3) aac
 4) aad
 5) aae
 6) aba
 7) abb
 8) abc
 9) abd
10) abe
11) aca
12) acb
13) acc
14) acd
15) ace
16) ada
17) adb
18) adc
19) add
20) ade
21) aea
22) aeb
23) aec
24) aed
25) aee
26) baa
27) bab
28) bac
29) bad
30) bae
31) bba
32) bbb
33) bbc
34) bbd
35) bbe
36) bca
37) bcb
38) bcc
39) bcd
40) bce
41) bda
42) bdb
43) bdc
44) bdd
45) bde
46) bea
47) beb
48) bec
49) bed
50) bee
51) caa
52) cab
53) cac
54) cad
55) cae
56) cba
57) cbb
58) cbc
59) cbd
60) cbe
61) cca
62) ccb
63) ccc
64) ccd
65) cce
66) cda
67) cdb
68) cdc
69) cdd
70) cde
71) cea
72) ceb
73) cec
74) ced
75) cee
76) daa
77) dab
78) dac
79) dad
80) dae
81) dba
82) dbb
83) dbc
84) dbd
85) dbe
86) dca
87) dcb
88) dcc
89) dcd
90) dce
91) dda
92) ddb
93) ddc
94) ddd
95) dde
96) dea
97) deb
98) dec
99) ded
100) dee
101) eaa
102) eab
103) eac
104) ead
105) eae
106) eba
107) ebb
108) ebc
109) ebd
110) ebe
111) eca
112) ecb
113) ecc
114) ecd
115) ece
116) eda
117) edb
118) edc
119) edd
120) ede
121) eea
122) eeb
123) eec
124) eed
125) eee







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal