optimize all possible combinations of integers

Question

Let's say I have a row vector composed of 5 integers, where the first integer is int1 and the second is int2

int1   int2   int3   int4   int5

and i want to create a list of all possible combinations assuming each one of the integers can be between 1 and 99.

One possibility would be to write 5 nested loops:

my list = []

for i in range(1,99):
    for j in range(1,99):
        for k in range(1,99):
            for l in range(1,99):
                for m in range(1,99):
                    my_list.append([[m,l,k,j,i]])

This would be pretty inefficient, and we would need 9,509,900,499 iterations.

is there a more efficient way of adding all possible combinations to a list (i.e. an alternative to 5 nested loops)?

i will write the code in python but the response needs not be python specific.

If there are 9,509,900,499 combinations, there is no way around the fact that you need to add 9,509,900,499 items to the list. — Blorgbeard, Jan 24 '18 at 22:14
you are right. but is there a faster way to generate all combinations than 5 nested loops? maybe I should correct the question — Alejandro Simkievich, Jan 24 '18 at 22:16
Nesting a loop doesn't make it slower. Nested loops are considered "slow" because the total number of iterations gets large quickly. But you have a specific number of iterations that need to execute. You could write out 9,509,900,499 separate `append` statements and it would not be measurably faster (ignoring problems caused by loading such a large program!). — Blorgbeard, Jan 24 '18 at 22:18
Possible duplicate of [Python nested looping Idiom](https://stackoverflow.com/questions/13885234/python-nested-looping-idiom) — L3viathan, Jan 24 '18 at 22:20
Although note that there are simpler ways to write the program: see https://docs.python.org/3/library/itertools.html — Blorgbeard, Jan 24 '18 at 22:20
not necessarily in a list - but I need them all to perform a follow on function — Alejandro Simkievich, Jan 24 '18 at 22:23
in terms of possible duplicate, I believe the other question is asking if there is a more elegant way to write something like this. I am asking if there is a more computationally efficient way of coming up with all combinations — Alejandro Simkievich, Jan 24 '18 at 22:24
yep, i do not need to hold the list in memory, actually I can do something with each combination and move on — Alejandro Simkievich, Jan 24 '18 at 22:33
Possible duplicate: https://stackoverflow.com/questions/3099987/generating-permutations-with-repetitions-in-python — jpp, Jan 24 '18 at 22:40
99% of the time, questions like this are an XY problem. I suggest you try to convince us that you're in the remaining 1%. — Stefan Pochmann, Jan 24 '18 at 22:43
it is not a duplicate, I am asking about efficiency gains - and I actually found one. not sure why I was voted down. — Alejandro Simkievich, Jan 24 '18 at 22:43
well, I just wrote a response I had to come up with it myself :). but that is the type of efficiency gain I am looking for. — Alejandro Simkievich, Jan 24 '18 at 22:45
If you're not even interested in better solutions then that makes me suspect even more that they exist. — Stefan Pochmann, Jan 24 '18 at 22:50
Just for simplicity, let's assume that you are not going to change the list after filling it. There is a limited number of actions you can do with that list: check whether some tuple of 5 integers is in the list, iterate through all tuples in the list... You can do all that without actually ever creating a list of 99^5 integers! — zvone, Jan 24 '18 at 23:34
Don't edit your question after other people have answered to tailor it to your own answer. — Blorgbeard, Jan 25 '18 at 17:44
Blorgbeard live and let live pal. chill out. I did not edit anything. go drink a beer. — Alejandro Simkievich, Jan 26 '18 at 18:57

zvone · Answer 1 · 2018-01-25T17:32:27.277

2

Taking this important comment into account, there is a simple solution:

yep, i do not need to hold the list in memory, actually I can do something with each combination and move on – Alejandro Simkievich

All you have to do is:

import itertools
my_list = itertools.product(xrange(1,99+1), repeat=5)

This executes in a fraction of a second and takes almost no memory. It does not actually create a list of 99^5 integers. Actually, it does not even create list of 99 integers. It fakes all of it.

Even though there is no list in the memory, my_list can be iterated through as if it was such a list:

for int1, int2, int3, int4, int5 in my_list:
    # do_whatever, but this will be executed 9509900499 times, of course
    # try e.g.
    print int1, int2, int3, int4, int5

edited Jan 25 '18 at 17:32

answered Jan 24 '18 at 23:42

zvone

18,045
3
49
77

1

This is nicer code than OP's; but I note that it's functionally identical to his 5 nested loops, as long as the inner code is processing the set of ints without storing them. – Blorgbeard Jan 25 '18 at 00:54
@Blorgbeard Unlike the OP's code, this (first code in my answer) does not spend hours to fill 70 GB of data into a list. Other than that, it is no better, but there is no way to optimize the core functionality which OP is hiding from us... The second code is a loop which shows that this can be used just like the list. I've updated my answer to explain that better (hopefully) – zvone Jan 25 '18 at 17:32
I know - my point was that the main improvement in your answer can be applied to the 5 nested loops - `print` instead of `append`. itertools or 5 nested loops doesn't matter, "as long as the inner code is processing the set of ints without storing them". – Blorgbeard Jan 25 '18 at 17:42

score 0 · Answer 2 · answered Jan 24 '18 at 22:41

0

I just realized there may be a way to expedite this running things in parallel.

Let's say you have a machine with 99 cores, you could run four nested loops on 99 cores in parallel. in each one of the 99 cores, the first integer is a constant. you would have an efficiency gain of 100x (a bit less in practice I guess).

I actually have access to a machine with 128 cores, so this may be an option.

answered Jan 24 '18 at 22:41

Alejandro Simkievich

3,512
4
33
49

Sure; the same way you could use a machine with 11 cores to calculate groups of 9 starting digits in parallel for eg. I don't think that's particularly insightful though? In any case it still sounds like a duplicate of [this](https://stackoverflow.com/questions/10262138/how-do-i-multi-process-the-itertools-product-module) – neophlegm Jan 24 '18 at 22:52
I do not know if it is insightful, but it helps me solve the problem. none of the folks who bashed my question thought of it anyway. it could be a duplicate, I give you that. – Alejandro Simkievich Jan 24 '18 at 22:57
1

@AlejandroSimkievich Running on 99 cores, you could create 99 partial lists, yes. In the end, you would have to merge them, if you want to have one large list. Note also that (assuming any overhead), 99^5 integers require 70 GB of RAM on a 64 bit machine. Note also that there is absolutely no information stored in those 70 GB of memory. List of all combinations is not information. So, what is the purpose? – zvone Jan 24 '18 at 23:30
@zvone Good luck trying to get the actual purpose out of him. I tried but got the impression that he really doesn't want to tell. For some reason it apparently needs to remain secret. – Stefan Pochmann Jan 24 '18 at 23:37

optimize all possible combinations of integers

2 Answers2