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
– Paul R, Commented Sep 11, 2014 at 7: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
– Paul R, Commented Sep 11, 2014 at 7:09
Check this. Looks similar. stackoverflow.com/questions/20250789/… — peter.petrov
– peter.petrov, Commented Sep 11, 2014 at 7:13
@peter.petrov: I'm not sure that helps, as the OP's loops do not iterate from 0. — Paul R
– Paul R, Commented Sep 11, 2014 at 7:59

mkrakhin · Accepted Answer · 2014-09-11 08:19:05Z

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, 2014 at 8:19

answered Sep 11, 2014 at 7:51

mkrakhin

3,4861 gold badge24 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Dawood ibn Kareem Over a year ago

The question requires a single loop. I count three loops in your answer.

mkrakhin Over a year ago

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).

user4758246 Over a year ago

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.

mkrakhin Over a year ago

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 Over a year ago

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

|

Collectives™ on Stack Overflow

Writing nested for loops as while

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related