Java: Unknown number of 'for' loops [duplicate]

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
– Athanasios Kataras, Commented Jan 6, 2016 at 13:26
You just want to permute t. See e.g. stackoverflow.com/questions/4240080/… — dejvuth
– dejvuth, Commented Jan 6, 2016 at 13:30
@priydarshi-singh I came up with a different solution that I think you might want to check out - gist.github.com/timmattison/1d58a306e23f2ee4b7fb — Tim Mattison
– Tim Mattison, Commented Jan 6, 2016 at 13:44

Gaël J · Accepted Answer · 2016-01-06 13:28:55Z

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.

I searched the internet for recursive methods, but can't think about how it can be implemented here.

nicomp · Accepted Answer · 2016-01-06 14:00:38Z

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.

Collectives™ on Stack Overflow

Java: Unknown number of 'for' loops [duplicate]

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related