0

Good afternoon,

I am quite new to Python, and I have to solve a problem which has the need to try billions of hypothesis... More specifically I need to iterate a list of 440 elements, but I need to do it 8 times... (yes, the number os iterations is completly insane I know).

My machine is quite good, so I want to use the multiprocessing python functionalities to speed this up a lot.

Do you know any simple solution which would take profit from the processing capabilities from my machine?

Inputs:

ListPairs:

for ind1 in range(16,37):
    for ind2 in range(16,37):

        ListPairsAux = []

        ListPairsAux.append(ind1)
        ListPairsAux.append(ind2)

        ListPairs.append(ListPairsAux)

For the simplicity of the problem, you can assume that both len(list1[i]) and len(list2[i]) are integers and both are equal to 198. (In the real problem we will actually have 21 different integers, but all in the same order - meaning that they won't go much further than 198.

The for loops are the ones below:

for first in ListPairs:
    print(str(first))
    for second in ListPairs:
        for third in ListPairs:
            for fourth in ListPairs:
                for fifth in ListPairs:
                    for sixth in ListPairs:
                        for seventh in ListPairs:
                            sumA = first[0] + second[0] + third[0] + fourth[0] + fifth[0] + sixth[0] + seventh[0]
                            sumB = first[1] + second[1] + third[1] + fourth[1] + fifth[1] + sixth[1] + seventh[1]
                            for i in range(len(list1)):
                                if sumA == len(list1[i]) and sumB == len(list2[i]):
                                    List7 = []
                                    List7 = [first, second, third, fourth, fifth, sixth, seventh]
                                    ListsOut[i].append(List7)

                            for eighth in ListPairs:
                                sumA = first[0] + second[0] + third[0] + fourth[0] + fifth[0] + sixth[0] + seventh[0] + eighth[0]
                                sumB = first[1] + second[1] + third[1] + fourth[1] + fifth[1] + sixth[1] + seventh[1] + eighth[1]
                                for i in range(len(list1)):
                                    if sumA == len(list1[i]) and sumB == len(list2[i]):
                                        List8 = []
                                        List8 = [first, second, third, fourth, fifth, sixth, seventh, eighth]
                                        ListsOut[i].append(List8)

Thank you so much!

Improve this question
13
  • 8
    Billions of combinations? 440^8 is more like 10^21 combinations. That's something like 30000 CPU-years if we assume 1 ns per combination. I don't think you'll get through all of that without some help from a wealthy nation state. Commented May 14, 2017 at 15:19
  • 3
    This seems like an XY Problem. You seem to be solving some other problem very inefficiently. What is that problem? Commented May 14, 2017 at 15:20
  • Hi Mathias! Thanks for your quick reply to my post. So you think it is not feasible at all? Commented May 14, 2017 at 15:21
  • 1
    I think you should ask a question for better algorithm not for multithreading this one Commented May 14, 2017 at 15:22
  • This is a huge tree... Where on the first node you have 440 options you can make, and that will happen always (meaning that each node will then have 440 options). The condition to select an option, is the sum when we reach to the n-level 7 or 8. Which is actually what you can see in my code above. P.S.: Thanks a lot for your replies to my question. Commented May 14, 2017 at 15:26

2 Answers 2

Reset to default
1

The solution you post will probably never finish, since it would require going through more than 10^21 combinations of elements. Rather than using multiprocessing you should use a faster algorithm.

Using the list1, list2 and lists_out that you use in your question, we are looking for ways to combine integers between 16 and 36 so that they sum to the lengths of the sequences in list1 and list2. The combinations should be of 7 or 8 integers in the range [16, 36].

import itertools
def so43965562(list1, list2, lists_out, lower=16, upper=36):
    assert len(list1) == len(list2) == len(lists_out)
    for n in (7, 8):
        for i in range(len(list1)):
            # Find all combinations of n numbers in [lower, upper]
            # that sum to len(list1[i])
            combs1 = combinations_summing_to(lower, upper, n, len(list1[i]))
            # Find all combinations of n numbers in [lower, upper]
            # that sum to len(list2[i])
            combs2 = combinations_summing_to(lower, upper, n, len(list2[i]))
            for t1, t2 in itertools.product(combs1, combs2):
                result = [(v1, v2) for v1, v2 in zip(t1, t2)]
                lists_out[i].append(result)

The following function writes s as a sum of n integers between l and u.

def combinations_summing_to(l, u, n, s, suffix=()):
    """In which ways can s be written as the sum of n integers in [l, u]?

    >>> # Write 2 as a sum of 4 integers between 0 and 5.
    >>> print(list(combinations_summing_to(0, 5, 4, 2)))
    [(0, 0, 0, 2), (0, 0, 1, 1)]
    >>> # Write 5 as a sum of 3 integers between 0 and 5.
    >>> print(list(combinations_summing_to(0, 5, 3, 5)))
    [(0, 0, 5), (0, 1, 4), (0, 2, 3), (1, 1, 3), (1, 2, 2)]
    >>> # Write 12 as a sum of 3 integers between 0 and 5.
    >>> print(list(combinations_summing_to(0, 5, 3, 12)))
    [(2, 5, 5), (3, 4, 5), (4, 4, 4)]
    >>> # Write 34 as a sum of 2 integers between 16 and 36.
    >>> print(list(combinations_summing_to(16, 36, 2, 34)))
    [(16, 18), (17, 17)]
    """
    if n == 0:
        return (suffix,) if s == 0 else ()
    elif n == 1:
        return ((s,) + suffix,) if l <= s <= u else ()
    else:
        return itertools.chain.from_iterable(
            # Combinations summing to s where the last element is k
            combinations_summing_to(l, k, n - 1, s - k, (k,) + suffix)
            for k in range(u, l-1, -1)
            # Early bailout if you can't make s with all elements <= k
            if l * n <= s <= k * n)

You can run the solution as follows:

lists_out = [[]]
so43965562(list1=[[0]*(7*16+1)], list2=[[0]*(7*16+2)], lists_out=lists_out)
for result in lists_out[0]:
    print(result)
# Outputs the following two combinations:
# [(16, 16), (16, 16), (16, 16), (16, 16), (16, 16), (16, 16), (17, 18)]
# [(16, 16), (16, 16), (16, 16), (16, 16), (16, 16), (16, 17), (17, 17)]
lists_out = [[]]
n = 133
so43965562(list1=[[0]*n], list2=[[0]*n], lists_out=lists_out)
print(len(lists_out[0]))
# Outputs 1795769, takes about 2.5 seconds to run.

Note that the output size increases exponentially, starting at nothing when n = 7*16 = 112, so it will still take a long time to compute all the combinations when n = 198 as you write in your question.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Hi Mathias, thanks a lot for your answer! Your approach was pretty interesting, and with my level of Python I would never go that way, as you noticed. However my problem is still much more complicated, but I can share it with you in case you are interested about it. Once again, thank you!
I hope you at least realize that you can use a function like my "combinations_summing_to" instead of going through all numbers by brute force. Good luck solving whatever your underlying problem is.
I will use your approach/function, but I actually just need to use it once! So, I will use your function to get all the possible combinations, for all the 21 possible integers (I mean that your 'n' variable should have 21 different values). Than for each 'n' value, I will write the possible combinations (lists_out) into a file, so that I don't need to go through all that work all over again, and I just need to read the values from a file and save them into a List of Lists or a List of Tupples.
But the real interesting problem is going to come next... and in case you feel interested about it, I can share it with you. Thanks once again Mathias for your help and sharing your know how.
0

If you want the combinations(or permutations), check python itertools

https://docs.python.org/2/library/itertools.html#itertools.combinations

Otherwise modify your algorithm.

 for combination in itertools.combinations_with_replacement(ListPairs, 8):
     # combination is a tuple
     for i in combination:
           #check your condition
Improve this answer

3 Comments

@Mathias: Thanks for your suggestions. I will try it and see how it goes. I may discuss with you the second part of the algorithm, which will come after this one. Thanks once more!
@Joquim I think your comment is misplaced :D
Hi Harindu. Yes your are right... I was doing too many things at the same time, and did not even notice. Sorry :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.