Recursive function for embedded loops

Question

I would like to have a clean recursive function to generate the same result than

static List<String> l, out;

l=new ArrayList<String>();
l.add("A");l.add("B");l.add("C");l.add("D");l.add("E");l.add("F");
for (int i = 0; i < l.size(); i++) {
    for (int j = i+1; j < l.size(); j++) {
        for (int k = j+1; k < l.size(); k++) {
            for (int t = k+1; t < l.size(); t++) {
                StringBuffer buffer = new StringBuffer(50);
                buffer.append(l.get(i));
                buffer.append(l.get(j));
                buffer.append(l.get(k));
                buffer.append(l.get(t));
                out.add(buffer.toString());
            }
        }
    }
}

here there are 4 levels for example

I gave one try there http://pastebin.com/auSxQMHt

but it's not working (see the output, I don't get as many results)

thx

Is there any particular reason you'd rather do this as recursion rather than nested for? The recursion is going to be much uglier and harder to debug. See: http://stackoverflow.com/questions/1313642/simulating-nested-loops — Charles, May 31 '12 at 20:46
Can you provide some explanation? Purpose of this code? Because recursive method will be much less understandable than this iterable version I think. — Xeon, May 31 '12 at 20:47
If you search the web for "recursive combination method" or "cartesian power method" (IIRC) you'll find many examples, including some on SO. — Dave Newton, May 31 '12 at 20:49
@Xeon, I need these method to incrementally generate keys (that are first singletons, then ordered pairs, then ordered 3-tuple), these keys help to find content indesed by these keys, the goal is not to generate the complete PowerSet, as it's not likely that all keys are searched — , Jun 01 '12 at 06:39

Justin · Accepted Answer · 2012-05-31T22:58:47.173

Try this out, your index is off by one:

private static final void loops(int i, StringBuffer buffer, int level, int k, int size) {
        if  (level>=k){
            out.add(buffer.toString());
        } else {
            for (int j = i; j < size; j++) {
                StringBuffer buf = new StringBuffer(buffer);
                buf.append(l.get(j));
                loops(j+1, buf, level+1, k, size);
            }
        }
}

... main() ...
    int size = l.size();
    loops(0, new StringBuffer(50), 0, 4, size);
... main() ...

Here are the results:

p1: 194580 duration:334 ms
p2: 194580 duration:370 ms

Instead of using "int j = i + 1" use "int j = i" and pass "loops(j+1, buf, level+1, k);"

Recursive function for embedded loops

1 Answers1