A recursive backtracking problem

Question

Ok, the real problem is slightly more complicated because it uses some classes that I've written instead of Strings, but it can be imagined like this: If you have a list of 700ish 3-letter words, how can I find every combination that can be formed by linking 5 of these words together by their first and last letters, i.e., CAT TOW WAR RAD DOG would be a success but so would CAT TOW WAR RAG GOD, and so on.

So far I have something like this:

for(int i = 0; i < list.size(); i++){
    String temp = chainMaker(list.get(i), list, used, temp);
}

public String chainMaker(String toAdd, ArrayList<String> unused,
    ArrayList<String> used, String result){

    if(result.size() >= 15)
        return result;
    else{
        if(result.canAdd(toAdd))
            result.add(toAdd);
        used.add(toAdd);

        return chainMaker(unused.remove(0), unused, used, result);
    }

    return result;
}

But this just keeps adding the producing rubbish. I'm terrible at recursive backtracking and I think that if I can just make this example work, I'll finally understand this concept. Please help me smart people!

Answer 1

Since you are looking at every combination, you will want to look at tree and graph traversal algorithms. They work well and allow you to use proven algorithms. Given that you have the "letter linking" constraint, you will also want to focus on the traversal algorithms that use heuristics or rules in the traversal. I am sure there are other more advanced ways to do this, but with the small dataset trees and graphs could work.

Answer 2

Here's a C++ implementation, but I think the logic is obvious. Just ask if you don't understand something.

void letterChain(string stack[5], int k, const vector<string> &words)
{
    if ( k == 5 ) // have 5 words, print solution
    {
        for ( int i = 0; i < 5; ++i )
            cout << stack[i] << " ";
        cout << endl;

        return;
    }

    for ( int i = 0; i < words.size(); ++i ) // try to put a word at the current level of the stack
    {
        // if words[i] is already used, we cant use it again (if we can, just remove this part)
        bool used = false;
        for ( int j = 0; j < k; ++j )
            if ( stack[j] == words[i] )
                used = true;

        if ( !used ) // remove this if you can use a word multiple times
        {
            if ( k == 0 || words[i][0] == stack[k - 1][2] ) // if the letters match
            {
                stack[k] = words[i]; // add it to the stack
                letterChain(stack, k + 1, words); // recursive call
            }
        }
    }
}

int main()
{
    vector<string> words;
    words.push_back("CAT");
    words.push_back("TOW");
    words.push_back("WAR");
    words.push_back("RAD");
    words.push_back("DOG");
    words.push_back("GOD");
    words.push_back("RAG");
    words.push_back("RAR");

    string stack[5];

    letterChain(stack, 0, words);
}

CAT TOW WAR RAD DOG
CAT TOW WAR RAG GOD
CAT TOW WAR RAR RAD
CAT TOW WAR RAR RAG
TOW WAR RAD DOG GOD
TOW WAR RAG GOD DOG
TOW WAR RAR RAD DOG
TOW WAR RAR RAG GOD
WAR RAR RAD DOG GOD
WAR RAR RAG GOD DOG

If you can only use a word as many times as it appears in the list, then just use a counting vector subtract the count of that word every time you use it.

Answer 3

Here is my try in Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class So3206795 {

  static void step(List<String> result, List<String> unused, String requiredStart) {
    if (result.size() == 3) {
      System.out.println(result);
      return;
    }

    for (int i = 0; i < unused.size(); i++) {
      String s = unused.get(i);

      if (s.startsWith(requiredStart)) {
        unused.remove(i); // will be put back later
        result.add(s);

        step(result, unused, s.substring(s.length() - 1));

        result.remove(result.size() - 1);
        unused.add(i, s);
      }
    }
  }

  public static void main(String[] args) {
    List<String> words = Arrays.asList("CAT", "TOW", "WAR", "RAG", "GOD", "ROR");
    // make a modifiable copy of the words
    List<String> unused = new ArrayList<String>(words);
    step(new ArrayList<String>(), unused, "");
  }
}

Answer 4

The following is based on my mis-reading your post. I'll leave it in to entertain you. The real solution is at the end of the post.

---

Are you sure that you want to calculate all possibilities of 5 words from a pool of 700 objects?

Here is my class to solve this problem:

public class SO3206795 {

    private static long ct;
    private static List<String[]> allPossibleWords(final Set<String> words, final String[] chain) {
        final List<String> usedWords = Arrays.asList(chain);
        final int offset = usedWords.lastIndexOf(null);
        List<String[]> wordsList;
        if (offset < 0) {
            wordsList = Collections.singletonList(chain);
            logCreated();
        } else {
            wordsList = new ArrayList<String[]>();
            for (final String word : words) {
                final String[] copy = Arrays.copyOf(chain, chain.length);
                if (!usedWords.contains(word)) {
                    copy[offset] = word;
                    wordsList.addAll(allPossibleWords(words, copy));
                }
            }
        }
        return wordsList;
    }

    private static List<String[]> getChains(final Set<String> words, final int length) {
        final List<String[]> tmpChain = new ArrayList<String[]>();
        final String[] chain = new String[length];
        tmpChain.addAll(allPossibleWords(words, chain));
        return tmpChain;
    }
    private static Set<String> getWords(final int count, final int letters) {
        final Set<String> set = new TreeSet<String>();
        final int[] arr = new int[letters];
        int tempCt = 0;
        while (tempCt++ < count) {
            set.add(nextWord(arr));
            for (int i = letters - 1; i >= 0; i--) {
                if (arr[i] == 25) {
                    arr[i] = 0;
                } else {
                    arr[i] = arr[i] + 1;
                    break;
                }
            }
        }
        return set;
    }

    private static void logCreated(){
        if(++ct%10000==0){
            System.out.println("Created "+ct+" chains");
        }
    }

    public static void main(final String[] args) {
        String[]usedArgs=args;
        if(args.length==1&&args[0].matches(".*\\D.*")){
            usedArgs=args[0].split("\\D+");
        };
        final int[] values = {10,3,5};
        for (int i = 0; i < usedArgs.length&&i<values.length; i++) {
            values[i] = Integer.parseInt( usedArgs[i]);
        }
        final SO3206795 thing = new SO3206795(values[0],values[1],values[2]);
        for (final String[] chain : thing.chains) {
            System.out.println(Arrays.toString(chain));
        }
    }

    private static String nextWord(final int[] arr) {
        final char[] ch = new char[arr.length];
        for (int i = 0; i < arr.length; i++) {
            final int j = arr[i];
            ch[i] = (char) (65 + j);
        }
        return new String(ch);
    }

    private static void printInfo(final int numberOfWords, final int wordLength, final int chainLength) {
        BigInteger words = BigInteger.valueOf(numberOfWords);
        for(int i = 1; i < chainLength; i++){
            words=words.multiply(BigInteger.valueOf(numberOfWords-i));
        }

        System.out.println(MessageFormat.format(
            "Creating {0} words of length {1}.\nCreating all possible chains of {2} words.\nThat''s {3} chains in total",
            numberOfWords, wordLength, chainLength, words.toString()));
    }

    Set<String>     words;

    List<String[]>  chains;
    public SO3206795(final int numberOfWords, final int wordLength, final int chainLength) {

        printInfo(numberOfWords,wordLength, chainLength);
        this.words = getWords(numberOfWords, wordLength);
        this.chains = getChains(this.words, chainLength);
    }

}

It has a main method that you can call with up to three arguments:

• numberOfWords (the number of words that will be generated, default: 10)
• wordLength (word length, default: 3)
• chainLength (length of word chains, default: 5)

However, when I launch it with the values 700, 3, 5, the debug output is this:

Creating 700 words of length 3.
Creating all possible chains of 5 words.
That's 165680980516800 chains in total

That's rather a lot, wouldn't you say so? Well that's what 700 * 699 * 698 * 697 * 696 adds up to. Now if you're using your own objects rather than strings and let's say your objects are just 3 bytes each in size this means you'll have a memory consumption of

497042941550400 Bytes  or
485393497607 KB        or
474017087 MB           or
462907 GB              or
452 TB                 

I don't know about you, but that's way more RAM than my machine has, I'm afraid, and unfortunately it's very unlikely that your objects are only 3 Bytes each (And the created lists and arrays also need some significant memory). So I don't think computing all possibilities is a good idea, even if it was fun to code.

And it will take a long time, too. On my machine, creating 10000 chains takes about 16 ms. So for 165680980516800 chains that's a total duration of

2650895688268 ms      or
2650895688 sec        or
44181594 min          or
736359 hours          or
30681 days            or
84 years

That's not too long, perhaps, as Deep Thought took 7 1/2 million years to come up with the answer 42, but it's probably still longer than you'll be willing to wait.

Please: my math is awful, if somebody explains to me why this is all nonsense I'll be more than happy, but I am afraid I've got the numbers figured out correctly.

---

End of misunderstanding:

Darn, I missed the letter linking constraint. Here's my updated solution. Replace the method allPossibleWords above with these two methods:

private static List<String[]> allPossibleWords(final Set<String> words, final String[] chain) {
    final List<String> usedWords = Arrays.asList(chain);
    final int offset = usedWords.lastIndexOf(null);
    List<String[]> wordsList;
    if (offset < 0) {
        wordsList = Collections.singletonList(chain);
        logCreated();
    } else {
        wordsList = new ArrayList<String[]>();
        for (final String word : words) {
            if (!usedWords.contains(word)&&(offset==chain.length-1||isLegalNeighbor(word,usedWords.get(offset+1)))) {
                final String[] copy = Arrays.copyOf(chain, chain.length);
                copy[offset] = word;
                wordsList.addAll(allPossibleWords(words, copy));
            }
        }
    }
    return wordsList;
}
private static boolean isLegalNeighbor(final String left, final String right) {
    return left.charAt(left.length()-1)==right.charAt(0);
}

also, we'll replace getWords with a more random version

private static Set<String> getWords(final int numberOfWords, final int wordLength) {
    final Set<String> set=new TreeSet<String>();
    final Random r = new Random();
    while(set.size()<numberOfWords){
        final char[] ch = new char[wordLength];
        for (int i = 0; i < ch.length; i++) {
            ch[i]=(char) (65+r.nextInt(26));
        }
        set.add(new String(ch));
    }
    return set;
}

Now I actually get reasonable execution times for 200 words, but 700 words still creates an OutOfMemoryError after what seems like forever.

Anyway, here is the complete solution on pastebin.

And here is the corrected math:

There are approximately 362559479 possible combinations

700 * (699/26) * (698/26) * (697/26) * (696/26)

given an object size of 3 bytes that means a memory consumption of

1087678437 Bytes  or
1062185 KB        or
1037 MB           or
1 GB

On my machine, creating 10000 chains with letter linking takes about 500 ms. So for 362559479 chains that's a total duration of

181279739 ms      or
181279 sec        or
3021 min          or
50 hours          or
2 days            

These are still impressive numbers, I'd say