Java: Unknown number of 'for' loops

Question

I want to make a program that would un-jumble some words.
I need to try all possible combinations of the words that can be formed, and then check if it is contained in a String variable, named dict.

My code is:

public class UnJumble
{
    public static void main(String args[])
    {
        String dict = "cat, rat, mat dog, let, den, pen, tag, art,";

        String t = "tra";
        int l = t.length();
        for(int i=0; i<l; i++)
        {
              char a=t.charAt(i);
              t = t.replaceFirst(a+"","");
              l--;
              for(int j=0; j<l; j++)
              {
                    char b = t.charAt(j);
                    t = t.replaceFirst(b+"","");
                    l--;
                    for(int k=0; k<l; k++)
                    {
                          char c = t.charAt(k);
                          if(dict.contains(""+a+b+c+","))
                          {
                                System.out.println("\'"+a+b+c+"\' found.");
                                break;
                          }
                    }
                    l++;
                    t = new StringBuilder(t).insert(j,b+"").toString();
              }
              t = new StringBuilder(t).insert(i,a+"").toString();
              l++;
        }
    }
}

The variable t contains the word to be un-jumbled.

With this code, the output is:
'rat' found.
'art' found.

I think that I would need as many for loops as there as characters in the String t.

But I want to make it able to un-jumble words of an unknown length. So how can I achieve this?

I have tried searching on the Internet, and on SO. I found some answers on SO that are written in other programming languages which I don't understand.

A first loop with as many as the lowest of the two: Cominations of max words that could be made i.e. n letters can produce a certain number of combinations (search combinatorials for calculation), or the number of total dictionary words (whichever is lower). — Athanasios Kataras, Jan 06 '16 at 13:26
You just want to permute `t`. See e.g. http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string — dejvuth, Jan 06 '16 at 13:30
@priydarshi-singh I came up with a different solution that I think you might want to check out - https://gist.github.com/timmattison/1d58a306e23f2ee4b7fb — Tim Mattison, Jan 06 '16 at 13:44

score 0 · Answer 1 · answered Jan 06 '16 at 13:28

0

You should look for recursive methods.

For example, given a string str of n characters, you can write a function that basicaly do this :

List<String> compute(String str)
    // TODO : Handle case where str has only 1 character
    List<String> list = compute(str.substring(0,n-2))
    // TODO : Compute all combinations of str[n-1] with list
    return list;

I guess this can be improved a lot in some cases.

answered Jan 06 '16 at 13:28

Gaël J

11,274
4
17
32

I searched the internet for recursive methods, but can't think about how it can be implemented here. – dryairship Jan 06 '16 at 13:31

score 0 · Answer 2 · answered Jan 06 '16 at 14:00

There is a tricky way to do this without a for loop for each letter in your variable t, but it's code-intensive. You can set up a loop that counts in base n, where n is the length of t. Assume i is your counter: Each pass through that loop you use the individual digits in i as indices into t, then build a ' word' and test that word against your dictionary. You are using i two different ways: as a counter and as a set of digits that represent indices into your t.

For example, if your t has three letters then you want to count in base 3 like this: 012, 020, 021, 022, 100, 101, 110,111, and so forth. Now the logic needs to verify that your combination of digits is unique so you don't use a letter twice when you build a word.

It's a lot of work but the algorithm is correct. The benefit is that it works for strings of any length.

I know I will be voted down, but oh well.

Java: Unknown number of 'for' loops

2 Answers2