Writing nested for loops as while

Question

Is there a way to write something like this with a single (while-) loop?

for(int a = 0; a < u; a++)
    for(int b = a; b < u; b++)
        for(int c = b; c < u; c++)
           .
              .
                 .
                    for(int <n> = <n-1>, <n> < u; <n>++) {
                       // work
                    }

Usually I use recursion if I need something like this, so I guess it could be done with a stack but I would prefer a solution without stack (if it is possible).

Thank you in advance!

Depends on what programming language you are using - please tag appropriately. — Paul R, Sep 11 '14 at 07:02
Well no, e.g. there are definitely good C++ alternatives for this kind of structure, but for C and C-related languages (and probably Java, but I wouldn't know) it's not so clear what the alternatives might be, if any. If you want a language agnostic answer though, then the `language-agnostic` tag is useful. — Paul R, Sep 11 '14 at 07:09
Check this. Looks similar. http://stackoverflow.com/questions/20250789/dynamically-change-the-number-of-nested-for-loops — peter.petrov, Sep 11 '14 at 07:13
@peter.petrov: I'm not sure that helps, as the OP's loops do not iterate from 0. — Paul R, Sep 11 '14 at 07:59
@PaulR That doesn't matter. The general idea/question is the same. — peter.petrov, Sep 11 '14 at 08:27
@peter.petrov: seriously ? Perhaps you could explain how you would calculate the loop indices when the start index for each loop varies as per the OP's case ? — Paul R, Sep 11 '14 at 08:31

mkrakhin · Accepted Answer · 2014-09-11T08:19:05.763

2

Or you could do something like this, storing your indexes in array

int[] indexes = new int[n];
outer: while (true) {
    if (indexes[n-1] == u) {
        int indexesToChange = 1;
        while ((indexesToChange < n + 1) && (indexes[n - indexesToChange] >= (u-1)))
            indexesToChange++;
        if (indexesToChange == n+1)
            break outer;
        indexes[n - indexesToChange]++;
        for (int i = indexesToChange - 1; i > 0; i--)
            indexes[n - i] = indexes[n - indexesToChange];
    } else {
        // do something
        indexes[n-1]++;
    }
}

Haven't tested it, so could be errors in implementation. But I hope I drive the point home.

UPDATE
Tested and found bug. Now it's fixed and works as intended.

edited Sep 11 '14 at 08:19

answered Sep 11 '14 at 07:51

mkrakhin

3,386
1
21
34

The question requires a single loop. I count three loops in your answer. – Dawood ibn Kareem Sep 11 '14 at 08:25
I don't think that "single" loop is the exact requirement of question. What's most important here is that number of loops doesn't depend on n. It's kind of O(1) vs O(n). – mkrakhin Sep 11 '14 at 08:28
Single loop would be nice, though it was more of an idea and a solution with more than one loop works for me as well. – user4758246 Sep 11 '14 at 10:22
Not sure if single-loop solution exists. Because you have at least one main loop with O(u^n) iterations and in every iteration you should check n indices (that's another loop). – mkrakhin Sep 11 '14 at 10:32
Theoretically single-loop solution is possible if you could use n-digit in u-nary numeral system as counter, having possibility to access random digit in constant-time :D – mkrakhin Sep 11 '14 at 10:36
Yeah, I had the same thought, but I think it would be excessively complicated. Honestly, I do think that this is a very fine answer. It's good that OP is a bit flexible about having a single loop. – Dawood ibn Kareem Sep 11 '14 at 10:37

Writing nested for loops as while

1 Answers1