Unscramble Letters in Java - Get all possible combinations of the letters

Question

Solved: What I was asking was Solved but feel free to answer with alternate methods. here's the letter unscrambler made with the answer. Project Page

I am currently an AP Computer Science student. I have been working on a letter unscrambler that reads in a dictionary and prints a list of words possible with the letter set inputted. To this end I make a map with Map<String,Set<String>> in which "earth" would be entered under the key "aerht" and in the corresponding set.

Example How Would I generate all of these:
CAKE -> ACEK
A          C           E           K
AC        CE           EK               
ACE       CEK            
ACEK

AE       CK
AEK
ACK
AK

The problem I am running into is that that some key values aren't being checked as currently I take in a set of numbers and alphabetize the characters eg earth->aehrt yet this skips combos such as aht->hat or eht -> the.

So basically my Question would be how to simplify the process of obtaining all alphabetical combos contained in such a key. eg earth-> aehrt,a,ae,aeh,aehr,ah,ahr,ahrt,aer,aert and so on so that I can crossreference all these keys with those in the dictionary I read in. letters[] contains a,e,h,r,t in order. Also, test is an ArrayList of Set. Key is "aehrt".

for(int z = 0; z<key.length();z++) {
    Set<String> temp = new HashSet<String>();

    //s1 = t*s0 ∪ {t} ∪ s0 = {t}
    for(String str: test.get(z)) //t*s0
                str+=letters[z];

    test.get(z).add(letters[z]); //{t}  
    test.get(z).addAll(test.get(z-1));//s0
    test.get(z).addAll(temp);
}

Answer 1

Starting with alphabetized key, 'aehrt', you can find all possible combinations of letters using the following method:

1. start with:       S0 = {}
2. next, take a:   S1 = a⋅S0 ∪ S0 ∪ {a} = {a}
3. next, take e:   S2 = e⋅S1 ∪ S1 ∪ {e} = {ae, a, e}
4. next, take h:   S3 = h⋅S2 ∪ S2 ∪ {h} = {aeh, ah, eh, ae, a, e, h}
5. etc...

once you have S5 (the entire set of combinations) check them all against your map.

---

public static void main(String... args){     
    Set<String> set = new TreeSet<String>();
    String key = "aehrt";

    //S1 = c*S0 ∪ {c} ∪ S0
    for(int z = 0; z < key.length();z++) {
        Set<String> temp = new HashSet<String>();
        char c = key.charAt(z);        

        for(String str: set)
            temp.add(str + c); // ∪ c*S0
        set.add(c+"");         // ∪ {c}
        set.addAll(temp);      // ∪ S0
    }

    System.out.println(set);
}

output: [a, ae, aeh, aehr, aehrt, aeht, aer, aert, aet, ah, ahr, ahrt, aht, ar, art,
         at, e, eh, ehr, ehrt, eht, er, ert, et, h, hr, hrt, ht, r, rt, t]

Answer 2

Suppose you have String CAKE : All 4 digits distinct. Then you will ha ve combinations as 4C1 + 4C2 + 4C3 + 4C4 = 2^4 - 1 = 15

C A K E CA Ak KE EC CK CE CAK AKE KEC CKE CAKE .

If you write numbers from 1 to 2^4-1 , they will be 0001 0010 0011 0100 and so on. Map these numbers to your String CAKE . Wherever you find 0 that character would be empty.Example

0001 = _ _ _ E

0010 = _ _ K _

0011 = _ _ KE

0100 = _ A _ _

and so on. You will get all your combinations of CAKE. I wrote a program to illustrate that in java :

public class AllCombinations {
    public static void main(String[] args) {
        char c[] = new char[] {'C','A','K','E'};
        int t = (int) Math.pow(2, c.length);
        for(int i=1;i<t;i++) {
            String s = Integer.toBinaryString(i);
            String comb = getComb(s,c);
            System.out.println(comb);
        }
    }

    private static String getComb(String s, char[] c) {
        String comb = "";
        int len = s.length();
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i) == '1') {
                comb += c[len-i-1];
            }
        }
        return comb;
    }
}