Recursive function to generate all combinations of capitals in a word

Question

Hey there,

Does anyone know the logic behind creating a recursive function to generate all combinations of capitals in a given word? I'm trying to do this in Java... For exmaple, give it the word "ben" and it outputs:

Ben bEn beN BEn BeN bEN BEN

But for any length word... any help appreciated!

Thanks,

Ben

Answer 1

Here's a hint:

000 # ben
001 # beN
010 # bEn
011 # bEN
100 # Ben
101 # BeN
110 # BEn
111 # BEN

EDIT:

Some more hints:

• there are 2^n combination (where n is the length of your string);
• you can use String's toCharArray()

EDIT 2:

Since it is no homework, here's a little demo of how you could do it (iteratively) in Java:

import java.util.*;

public class Main {   
    public static void main(String[] args) {
        int n = 1;
        for(String combination : new CombinationIterator("ben")) {
            System.out.println((n++)+" = "+combination);
        }
        System.out.println("-------------");
        n = 1;
        for(String combination : new CombinationIterator("test?", "TEST!")) {
            System.out.println((n++)+" = "+combination);
        }
    }
}

class CombinationIterator implements Iterator<String>, Iterable<String> {

    protected final String zeros;
    protected final String ones;
    private int current;

    public CombinationIterator(String word) {
        this(word.toLowerCase(), word.toUpperCase());
    }

    public CombinationIterator(String zeros, String ones) {
        this.zeros = zeros;
        this.ones = ones;
        this.current = 0;
    }

    @Override
    public boolean hasNext() {
        return current < (int)Math.pow(2, zeros.length());
    }

    @Override
    public Iterator<String> iterator() {
        return this;
    }

    @Override
    public String next() {
        if(!hasNext()) {
            throw new NoSuchElementException("No such combintion: "+current+" in '"+zeros+"'");
        }
        char[] chars = zeros.toCharArray();
        for(int i = zeros.length()-1, bit = 1; i >= 0; i--, bit <<= 1) {
            if((bit & current) != 0) {
                chars[i] = ones.charAt(i);
            }
        }
        current++;
        return new String(chars);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Output:

1 = ben
2 = beN
3 = bEn
4 = bEN
5 = Ben
6 = BeN
7 = BEn
8 = BEN
-------------
1 = test?
2 = test!
3 = tesT?
4 = tesT!
5 = teSt?
6 = teSt!
7 = teST?
8 = teST!
9 = tEst?
10 = tEst!
11 = tEsT?
12 = tEsT!
13 = tESt?
14 = tESt!
15 = tEST?
16 = tEST!
17 = Test?
18 = Test!
19 = TesT?
20 = TesT!
21 = TeSt?
22 = TeSt!
23 = TeST?
24 = TeST!
25 = TEst?
26 = TEst!
27 = TEsT?
28 = TEsT!
29 = TESt?
30 = TESt!
31 = TEST?
32 = TEST!

Answer 2

In pseudo code (well, Python actually, but it's as close to pseudo code as a real language gets):

def recurse (pref,suff):
    # If no characters left, just print prefix.

    if suff == "":
            print pref
            return

    # Otherwise add lowercase of first suffix letter to prefix
    # and recur with that and the remainder of the suffix.
    # Then do the same for uppercase.
    # If you wanted smarts, this is where you'd detect if the
    # upper and lower were the same and only recurse once.

    recurse (pref + suff[0:1].lower(), suff[1:])
    recurse (pref + suff[0:1].upper(), suff[1:])

# Test the function with "Ben".

recurse ("","beN")

This outputs:

ben
beN
bEn
bEN
Ben
BeN
BEn
BEN

The way it works is relatively simple (most recursive solutions are once you understand them).

The starting condition is when you have no prefix and a suffix that you need to iterate over to get all the different possibilities of mixed case.

The terminating condition is simply when there's no letters left to select two cases for.

Every other condition you simply recur twice, once with the lower case letter and once with the upper.

Keep in mind that this will not handle non-alpha characters properly, it's only meant to show you how the logic works. For example for the string "a!", you will get four lines of output even though "!" is the same in upper and lower case.

For proper handling of that, you would use:

def recurse (pref,suff):
    # If no characters left, just print prefix.

    if suff == "":
            print pref
            return

    # Otherwise add lowercase of first suffix letter to prefix
    # and recur with that and the remainder of the suffix.
    # Then do the same for uppercase.
    # We also detect if the upper and lower are the same
    # and only recurse once.

    if suff[0:1].lower() == suff[0:1].upper():
        recurse (pref + suff[0:1], suff[1:])
    else:
        recurse (pref + suff[0:1].lower(), suff[1:])
        recurse (pref + suff[0:1].upper(), suff[1:])

# Test the function with "Ben!!!".

recurse ("","beN!!!")

which only gives 8 lines instead of 64.

The equivalent in Java, since this isn't homework, is:

public class test {
    public static void recurse (String pref, String suff) {
        if (suff.length() == 0) {
            System.out.println (pref);
            return;
        }

        String first = suff.substring(0,1);
        String rest = suff.substring(1);

        if (first.toLowerCase().equals(first.toUpperCase())) {
            recurse (pref + first, rest);
        } else {
            recurse (pref + first.toLowerCase(), rest);
            recurse (pref + first.toUpperCase(), rest);
        }
    }

    public static void main(String[] args) {
        recurse ("","beN!!!");
    }
}

Answer 3

The list of outputs for "ben" can be made by concatenating the following two lists:

• adding "b" to the beginning of each of the items in the list of outputs for "en"
• adding "B" to the beginning of each of the items in the list of outputs for "en"

You could base your recursive definition on this approach.