Generate All Possible Words of Length n

Question

Given:

Some characters in input String.
An integer N

How can I generate all possible words that has the exact length of N?

If I have input = {"a", "b", "a"} and N=2, then the output should be: ab,aa,ba (without the duplicates)

I searched for this, and all I got is some algorithms that I couldn't understand rather that implement. I understand that I need to implement a recursive method, but I'm stuck at the point after the stop condition.

public void generate(String input, int length) {        
    if(length == 0) {
        System.out.println(input);
        return;
    }
    //Not sure about this part
    String[] a = input.split("");
    for(int i =0; i<a.length; i++) {
        loop(input+a[i], length-1);
    }
}

Have you looked [At this solution][1] ? [1]: http://stackoverflow.com/questions/2673494/generate-all-words-using-java?rq=1 — Gabriel Kohen, Jul 19 '13 at 18:13
@DanielGruszczyk No. If acharacter is listed once then it can't appear twice. — iTurki, Jul 19 '13 at 18:14
@iturki you defined that input is a set, a set doesn't have repeats. — roippi, Jul 19 '13 at 18:15
If there are K symbols and no restrictions then there are pow(K,L) words of length L. This suggests a mapping from integers N=0..(pow(K,L)-1) into words where one finds the base K representation of a number N and then replaces the digits with the symbols. — Paul, Jul 19 '13 at 18:17
See my answer [here](http://stackoverflow.com/questions/12288836/given-a-length-and-a-set-of-characters-how-to-get-all-the-possible-string-combi/12288895#12288895) for generating the values, then use a `HashSet` to ignore duplicates. — Brian, Jul 19 '13 at 18:19
Also a good resource: [Combinatorial Algorithms](http://www.martinbroadhurst.com/combinatorial-algorithms.html) — Brian, Jul 19 '13 at 18:22
@Brian This will take time if you have -as in my real case- a list of 12 chars and N can go up to 10! — iTurki, Jul 19 '13 at 18:24
Given the nature of your issue, I think most solutions are going to take quite a few iterations — StephenTG, Jul 19 '13 at 18:26
@GabrielKohen This is the closest thing to my situation. Thanks for sharing. — iTurki, Jul 19 '13 at 18:27
@Brian Besides, I'm expecting inputs in all languages, not English only. So, iterating won't do it. — iTurki, Jul 19 '13 at 18:34

score 1 · Answer 1 · answered Jul 20 '13 at 07:10

This should do the trick and work with any input and N. Behavior is not well defined for N = 0 or N > input.length()

public static void generate(String input, int N) {
    generate("", input, new HashSet<String>(), N);
}

private static void generate(String str, String input, Set<String> dup, int N) {
    if (str.length() == N && dup.add(str))
        System.out.println(str);
    else
        //remove a char form input and add it to str
        for (int i = 0; i < input.length(); i++)
            generate(
                str + input.charAt(i), 
                input.substring(0, i) + input.substring(i + 1), 
                dup, N);
}

This has been adapted from the more general "calculate all permutation" problem. In the general problem there is no duplicate check and str is printed when input.isEmpty(). Let me know if you need any clarifications.

score 0 · Answer 2 · answered Jul 20 '13 at 13:49

This works well also for empty strings or n == 0.

The heavylifting is in the second overload combination() method (the one that takes four parameters). The first overload simply translates the input string into a List<Character> and prepares an empty hash-set where the results are stored:

Set<String> combination(String input, int n) {
  List<Character> letters = new ArrayList<Character>();
  for (int i = 0; i < input.length(); ++i)
    letters.add(input.charAt(i));
  Set<String> results = new HashSet<String>();
  combination("", letters, n, results);
  return results;
}

void combination(String soFar, List<Character> letters, int n, 
    Set<String> results) {
  if (n == 0) { 
    results.add(soFar);
    return;
  }

  int startIndex = soFar.length();
  if (startIndex >= letters.size())
    return;      

  for (int i = startIndex; i < letters.size(); ++i) {
    // ch is the next candidate to add to the result that we're 
    // building (soFar)
    char ch = letters.get(i); 
    // Swap the characters at positions i and position startIndex.
    char temp = letters.get(startIndex);
    letters.set(i, temp);
    letters.set(startIndex, ch);

    // add ch to soFar, compute combinations of length n-1.
    // as startIndex is essentially soFar.length() this means that 
    // the recursive call will only process the remainder of the list.
    combination(soFar + ch, letters, n - 1, result);

    // Swap the characters back - restore the original state.
    letters.set(i, ch);
    letters.set(startIndex, temp);
  }

Generate All Possible Words of Length n

2 Answers2