1

I have a list of 11 numbers, and I want to test the product of all combinations against some rule (2^11 possibilities).

I came across this SO question, but it seems to return a list of all combinations, which I think would take up to much memory.

My C++ thinking would be to go through each binary number 0x001 to 0x7FF and multiply each number where its corresponding bit is 1.

Example with 4 numbers: My list is [2, 3, 5, 7]

The first binary number would be 0001 giving - 2 = 2

Later we would get to 1110 and the product would be 3 * 5 * 7 = 105

Is there a better way of doing this in python? A bit manipulation doesn't seem like the right way to go.

Davide Fiocco
  • 5,350
  • 5
  • 35
  • 72
MikeS159
  • 1,884
  • 3
  • 29
  • 54
  • @Bazingaa thanks for the edit. Had some weird formatting bug going on, posted on meta https://meta.stackoverflow.com/questions/373704/what-is-going-on-here-there-is-no-code – MikeS159 Sep 06 '18 at 09:47
  • 1
    Yes, you are correct. There are 11! combinations of the list ordering, but order doesn't matter for multiplication so it would reduce to 2^11. – MikeS159 Sep 06 '18 at 09:59
  • `itertools.permutations` returns an **iterable** (**not** a list), so you don't have to worry about memory. – CristiFati Sep 06 '18 at 10:02

1 Answers1

3

A solution that should work with long lists without memory problems (with a "functional" approach) that uses iterables is:

import itertools
from functools import partial
import numpy as np

my_list = [1,3,5,7,9,11,13,15,17,19,21]

# define helper partial function useful to return an iterable of combinations with r elements
combinations_with_r = partial(lambda r: itertools.combinations(my_list, r = r))

# generate all combinations, print them with their products
for r in map(combinations_with_r, range(1, len(my_list) + 1)):
    for j in r:
        print(j, np.prod(j))

You can declare my_list = np.array([1,3,5,7,9,11,13,15,17,19,21], dtype = 'int64') to mitigate overflow problems.

Davide Fiocco
  • 5,350
  • 5
  • 35
  • 72
  • If I count the permutations in where you print `j, np.prod(j)` it comes out at 2046 which seems to low. Some results of np.prod are also giving negative numbers. Is numpy using signed ints underneath? – MikeS159 Sep 06 '18 at 10:48
  • Hi! They should be 2^11 = 2048. I haven't seen negative products in my output, can you give an example of a combination of an example `my_list` behaving that way? – Davide Fiocco Sep 06 '18 at 10:57
  • Sorry, the count is correct. Some examples below of negatives (2, 3, 5, 7, 11, 13, 17, 23, 29, 31) 1965880678 (2, 3, 5, 7, 11, 13, 19, 23, 29, 31) -1087225998 (2, 3, 5, 7, 11, 17, 19, 23, 29, 31) -1752139174 (2, 3, 5, 7, 13, 17, 19, 23, 29, 31) 1052902646 (2, 3, 5, 11, 13, 17, 19, 23, 29, 31) -1413272482 (2, 3, 7, 11, 13, 17, 19, 23, 29, 31) 1457392362 (2, 5, 7, 11, 13, 17, 19, 23, 29, 31) -1865980026 (3, 5, 7, 11, 13, 17, 19, 23, 29, 31) 1495997257 – MikeS159 Sep 06 '18 at 11:03
  • 1
    For some reason my version on numpy seems to be working with signed 32 bit ints. (2, 5, 7, 11, 13, 17, 19, 23, 29, 31) -1865980026 Should be 66,853,496,710 Subtracting 2^31 32 times leave us with -1865980026 – MikeS159 Sep 06 '18 at 11:51
  • Doesn't overflow on my environment, but maybe declaring `my_list = np.array([1,3,5,7,9,11,13,15,17,19,21], dtype = 'float64')` might give a bit extra leeway on yours (?). – Davide Fiocco Sep 06 '18 at 12:02
  • That worked thanks, although I used int64 in the end not float. Edited the answer to reflect this – MikeS159 Sep 12 '18 at 09:17