4
\$\begingroup\$

In python the itertools module is a good tool to generate combinations of elements. In this case I want to generate all combinations (without repetition) having a subsets of specified length but also with a product limit. For example, given a list of integer numbers I want all subsets of length 4 which product is bellow a given numerical limit, like bellow:

import functools, operator
LST = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ]
prod = lambda A : functools.reduce(operator.mul, A )

def combinations_with_limit( LST, length,lim ) : 
''':Description: LST - array of integers, 
    length = number of elements in each subset , 
    lim = product limit of each subset '''

    H = list(range(length))         # H - represents the index array
    B = [ LST[ii] for ii in H ]     # B - the main array with elements
    while H[0] <= len(LST)-length  :
        for i in range( H[-1], len(LST)) :
            H = H[:-1] + [i]
            B = [ LST[ii] for ii in H ]
            if prod(B) > lim :      ###  LIMIT THE OUTCOME PART . It skips the rest of the iteration
                H[-1] = len(LST) - 1
            elif prod(B) <= lim :
                yield B
            if H[-1] == len(LST) - 1 :    # We reset the index array here
                j = len(H)-1
                while H[j] == len(LST)-length+j :
                    j -=1
                H[j] +=1
                for l in range(j+1, len(H)) :
                    H[l] = H[l-1] +1

for i in combinations_with_limit(LST, 4 , 1000 ) :
    print(i ,end='  ' )

The output will look as follows:

[2, 3, 5, 7]  [2, 3, 5, 11]  [2, 3, 5, 13]  [2, 3, 5, 17]  [2, 3, 5, 19] 
[2, 3, 5, 23]  [2, 3, 5, 29]  [2, 3, 5, 31]  [2, 3, 7, 11]  [2, 3, 7, 13]  
[2, 3, 7, 17]  [2, 3, 7, 19]  [2, 3, 7, 23]  [2, 5, 7, 11]  [2, 5, 7, 13] 

And this is correct. All the products subsets are bellow the requested limit. However, I think that the above code is non-elegant and has some major loop inefficiency as I tested it for larger lists with > thousands of elements.

Do you have any ideas on how to improve it?

\$\endgroup\$
0
2
\$\begingroup\$

Welcome to Python programming!

Your code has various formatting issues, including the fact that when copying it here, you messed up the indentation of the docstring in your function – copying what you write here into my development environment will not work because of that. But let's look at the semantics.

On a high level view, this sounds like a problem I would try to solve recursively.

All the products of one number that are less than or equal to a target (you don't state that equal-to is permitted, but the line if prod(B) > lim : makes me think that is what you want) are exactly the numbers n <= limit, and from there we can generalize to implementing ‘The product of k numbers ≤ p if x is the first number and the product of the remaining k-1 numbers ≤ p//x.’ Note that this works with integer division – If you allow floats or if your limit is exclusive, you need float division.

For that recursive solution, I would use a generator and yield every partial solution up the call chain until I get to the original loop that wants my results.

But let us assume that, for whatever reason, you indeed want a function that solves this iteratively, not recursively.

Then, even before I look at your function, it has issue: 2*3*11*13 = 858 < 1000, but that combination does not appear in your list, so you would do well trying to manually generate maybe two examples where you know the answer, and try to produce them using your function.

If you feel it difficult to use the mental arithmetics, trust the tools you mention:

def combinations_with_limit(lst, length, lim):
    return [x for x in itertools.combinations(lst, length)
            if prod(x) <= lim]

is quite a readable and explicit process. It might throw away a lot of things, but it should help you get test cases.

Once you have a working solution, there are several things in your code to look out for.

  • Calculating the product separately for various combinations, and even twice in your middle loop, will be expensive. Store it somewhere and manipulate it while moving about, instead of running prod too often, in particular if you have a need to access it twice, like in your if and elif.
  • You are manipulating both H and B in parallel. That feels dangerous: You need great care to make sure that H goes through all combinations, keeping the right length, and never gains any duplicate elements, and then you add the computational overhead of a full list comprehension on top to generate your Bs. That sounds easy to get wrong, and as your results show, one of the conditions indeed goes wrong.
\$\endgroup\$
1
\$\begingroup\$

Pass 1

Here is some example code; it changes nothing about your algorithm:

from functools import reduce
from operator import mul
from typing import Iterable, List, Sequence


def prod(a):
    return reduce(mul, a)


def combinations_with_limit(
    lst: Sequence[int], 
    length: int, 
    lim: int
) -> Iterable[List[int]]:
    """:Description: LST - array of integers,
    length = number of elements in each subset ,
    lim = product limit of each subset"""

    H = list(range(length))         # H - represents the index array
    B = [lst[ii] for ii in H]       # B - the main array with elements
    while H[0] <= len(lst) - length:
        for i in range(H[-1], len(lst)):
            H = H[:-1] + [i]
            B = [lst[ii] for ii in H]

            # Limit the outcome part. It skips the rest of the iteration
            if prod(B) > lim:
                H[-1] = len(lst) - 1
            elif prod(B) <= lim:
                yield B
            if H[-1] == len(lst) - 1:  # We reset the index array here
                j = len(H) - 1
                while H[j] == len(lst) - length + j:
                    j -= 1
                H[j] += 1
                for l in range(j+1, len(H)):
                    H[l] = H[l-1] + 1


print('  '.join(
    str(c) for c in 
    combinations_with_limit(
        (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31),
        4, 1000
    )
))

Things to note:

  • Standard PEP8 indentation in more places
  • Type hints to clarify function signature
  • Don't use a lambda when a plain function will suffice
  • Use join for the output
  • Use a tuple for input since we don't need to mutate it

Tests

Using your original function as well as the solution from anaphory, write a basic test:

def test():
    inp = ((2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31), 4, 1000)
    ref = tuple(anaphory(*inp))
    for alt in (original,):
        act = tuple(tuple(li) for li in alt(*inp))
        refs, acts = set(ref), set(act)

        miss_r = acts - refs
        miss_s = refs - acts
        len_diff = len(act) != len(ref)
        if miss_r or miss_s or len_diff:
            print(f'Method {alt.__name__} failed -')
            if miss_r:
                print('   ref missing from act:', miss_r)
            if miss_s:
                print('   act missing from ref:', miss_s)
            if len_diff:
                print(f'   Length mismatch: {len(act)} != {len(ref)}')
            print()


if __name__ == '__main__':
    test()

This demonstrates which values your method is missing - as indicated in the other answer, (2, 3, 11, 13).

Other improvements

  • Store len(lst) in a local variable for reuse
  • H = H[:-1] + [i] can be H[-1] = i, assuming there are no adverse effects of keeping the same list
  • elif prod(B) <= lim: should simply be else
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.