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

Answer 3

One way would be to continually increment a number where the bits of the number represent letters in your group. For example, for "earth", you'd go through all the nonzero 5-bit numbers, by counting from 1 to 31. Bit 0 could represent 'e' or 'h'; it doesn't really matter. Just be consistent.

At each step, find the set bits, and select the corresponding letters from your group. That's one of the possible subgroups. (You may need to use a HashSet or something to eliminate duplicates...for example if your group has 2 "e"s or something.) So for "earth", 1 might be "e", 2 might be "a", 3 would be "ea", 4 would be "r", and so on.

When your number is greater than or equal to (1 << the number of letters), you've exhausted all the possibilities.

Note, this doesn't give all the possible orderings/arrangements, just the possible groups. Hopefully you've arranged your data so that you can search by a string containing sorted characters.