itertools.combinations: Consume multiple times over intervals

Question

from itertools import combinations
from more_itertools import consume

k = 170
index_list = [16, 32, 48, 62, 76, 88, 100, 110, 120, 128, 136, 142, 148, 153, 158, 161, 164, 166]

for n in range(1, k+1):
    iterable = combinations(range(k), n)
    for output in iterable:
        print(output)

I am having iterables and a list containing indexes as shown above: The index_list is representing intervals: they go from 0 to 16, from 17 to 32, from 33 to 48 and so on. Last interval is 167 to k-1. When I loop a iterable, I want to skip multiple steps, whenever there are 2 values of the output within the same interval. Output (0, 1), for example: Both values are within the interval 0-16, so next output shall be (0, 17). The outputs afterwards would be (0, 18), (0, 19),..., (0, k-1) as these are not within a interval. Afterwards, the output will be (1, 2) which shall be skipped again and so on. And later, when the output is (17, 18) it shall skip to (17, 33). When n is 3, the very first output is (0, 1, 2) which then shall be skipped to (0, 17, 33). The consume-method provided by more-itertools allows one to step multiple elements ahead. Here it would be used like so:

consume(iterable, 20)    # skipping 20 steps ahead

I have managed it to get the wanted behavior for 2 elements in the output:

steps = 0
for i, out in enumerate(output):
    for j, index in enumerate(index_list):
        if out <= index:
            break
    try:
        if output[i + 1] <= index_list[j]:
            steps = steps + index_list[j] - output[i + 1]
    except:
        pass
consume(iterable, steps)

But for 3 elements and more the amount of steps is not calculated correctly anymore. It must be multiplied by some value but I don't know where to get it. Another task is, that I do not want to check for the intervals for every single output. When a consume was executed, it somehow must already know when the next consume-instruction will happen. Any help please?

I would like to clarify a little. If I use your code for the case n=2, then the last three pairs of numbers (167, 168), (167, 169), (168, 169). So should it be or is this a mistake? Shouldn't (167, 168) be the last value? — zanuda, Jun 11 '20 at 14:37
And one more question. After (0, 166, 169) what should go? (0, 167, 168), (1, 2, 3) OR (0, 167, 168), (1, 17, 33)? — zanuda, Jun 11 '20 at 14:42
The last interval represented by the index_list should be 167 to k-1. Sorry for the mistake, I will correct it. So, for n=2 I want the last tuple to be (166, 169), because 166 is the last value of the 2nd last interval and 169 is the last value of the last interval. After (0, 166, 169) it shall be (1, 17, 33). Thanks for looking into this :) — R2wo, Jun 12 '20 at 16:14
Ok. But I can’t understand why after (0, 169) comes (1, 2), but after (0, 166, 169) comes (1, 17, 33), and not (1, 2, 3). Anyway, I will offer you the code in the answer, it gives only valid pairs, that is, tuples with numbers from different ranges. Perhaps you will be able to change it so that it gives out intermediate pairs ((1, 2), (2, 3) and so on). Because after reading your answer, I realized that I did not fully understand the rules for the appearance of these intermediate tuples. — zanuda, Jun 13 '20 at 11:57
I meant that in my given example it will be (1, 2) after (0, 169) as there is a new iterable created. Best of course was when (1, 2) would not be outputted, but (1, 17) directly. I think with your answer below you exactly try to achieve what I wanted. — R2wo, Jun 13 '20 at 13:17

zanuda · Accepted Answer · 2020-06-14T13:48:24.197

1

This code only works when n < 20 (Because the number of statically nested blocks in Python is limited to 20)

k = 170
index_list = [16, 32, 48, 62, 76, 88, 100, 110, 120, 128, 136, 142, 148, 153, 158, 161, 164, 166]


def get_bound(x):
    for i in range(len(index_list)):
        if x <= index_list[i]:
            return index_list[i]
    return k


def valid_combs(i, n=None, comb=None):
    n = n if n is not None else i
    comb = comb or list(range(n))
    if i == n:
        for x in range(k):
            comb[0] = x
            yield from valid_combs(i - 1, n, comb)
    elif i >= 1:
        prev = comb[n - i - 1]
        bound = get_bound(prev)
        for x in list(range(bound + 1, k)):
            comb[n - i] = x   
            yield from valid_combs(i - 1, n, comb)
    else:
        yield tuple(comb)


for n in range(1, k+1):
    iterable = valid_combs(n)
    for output in iterable:
        print(output)

edited Jun 14 '20 at 13:48

answered Jun 13 '20 at 12:00

zanuda

176
1
6

When I try to run your code I get an IndexError in line 17: comb[0] = x Is it the same for you? – R2wo Jun 13 '20 at 13:11
Sorry, I missed 1 in the 'for n in range(1, k+1)'. I corrected now, please try again. And it is better to try the 'for n in range (1, 4)', for example, because function valid_combs works very long for large n values. – zanuda Jun 13 '20 at 14:44
I then found out that the maximum recursion depth for Python is 20 (https://stackoverflow.com/questions/44972719/why-does-python-have-a-limit-on-the-number-of-static-blocks-that-can-be-nested), so even though my algorithm is fundamentally correct, it will not work for n >= 20. So my answer cannot be recognized as true, the algorithm needs to be reviewed. – zanuda Jun 14 '20 at 06:34

itertools.combinations: Consume multiple times over intervals

1 Answers1