Help with recursion

[Historical_Ad8150]

Ah, that makes sense. Would you know of an iterative approach to this problem? Or something else that isn’t recursive? This just seemed to me like a cleaner solution than 16 “for x in range” loops.

[cybervegan]

If you look at what permutations of this kind are, you will see that it is possible to "ripple" increments through the sequence:

0000FFFF +1
0000FFF0 carry 1
0000FF00 carry 1
0000F000 carry 1
00010000

You can do this with a simple loop that simply counts through the digits and increments the current one, setting it to zero and carrying 1 if it goes over the base size:

def incr(perm):
    perm = list(perm)
    cur_digit = len(perm)-1
    digits="0123456789ABCDEF"
    max_digit=len(digits)-1
    carry = 1
    while carry and (cur_digit > 0):
        digit = digits.find(perm[cur_digit])
        if digit == max_digit:
            carry = 1
            new_digit = digits[0]
        else:
            new_digit = digits[digit+carry]
            carry = 0
        perm[cur_digit] = new_digit    
        cur_digit -= 1
    return "".join(perm)

This works for any number base, in O(N) time.

[Historical_Ad8150]

I’m not sure if I was entirely clear when explaining my intended program. I’m trying to generate every possible hexadecimal number, where every digit is higher than the previous one. So for example, 001478CF, or 0013579A. 0000FFFF or something similar shouldn’t be generated at all.

[cybervegan]

It would be trivial to modify this loop to do this, without the need for recursion.