Python Forum
All possible combinations - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: All possible combinations (/thread-31224.html)

All possible combinations - CODEP - Nov-29-2020

Hi,
I'm making a program that that takes a bunch of numbers from the user (for example: 2,8,9,21,67,9,2,4) and puts them into a list.
After that, the program needs to multiply the numbers from 1-1(2), 1-2(2*8), 1-3(2*8*9), 1-4(2*8*9*21)... and check if the answer for each equation is odd. When it gets to the end of the list, it needs to do the same thing starting from the second number:2-2(8), 2-3(8*9), 2-4(8*9*21)... When it does that, it starts from the third number while checking if the answer is odd. The program needs to do that for all possible combinations. Can anyone tell me how I should write my code that so it will be fast for a very high amount of numbers?

RE: All possible combinations - DPaul - Nov-29-2020

Maybe you can save a lot of time by observing some simple rules first:
- Multiply anything with an even number => result is even.
- Multiply 2 odd numbers = > result is odd.
Could you be more specific as to the desired output?

Paul

RE: All possible combinations - deanhystad - Dec-01-2020

Do you want the equation solutions or do you just want to know if the equation solutions are even or odd?

I started out by computing a list of partial products that can be reused.
pp = [1(2), 2(2*8), 3(2*8*9), 4(2*8*9*21), ...] and got this:

pp = [2, 32, 432, 12096, 1013040, 10940832, 25528608, 116702208]

Now I can use the pp to quickly calculate the results for each equation:

1-1(2) = 1 - pp[0]
1-2(2*8) = 1 - pp[1]
1-3(2*8*9) = 1 - pp[2]
1-4(2*8*9*21)= 1 - pp[3]

And for other rows
2 - 2(2*8) = 2 - pp[1]
3 - 3(2*8*9) = 3 - pp[2]
etc...

If you are only interested knowing if the result of the equations are even or odd, we can simplify things further. Instead of keeping the numerical value of the partial products I put True if the pp is even and False if the pp is odd.

pp = [True, True, True, True, True, True, True, True]

Now I can test using boolean logic. If the index is even and the pp is even, the result of index - pp is even. If the index is odd and the pp is odd, the result of index - pp is even. If the index is even and the pp odd, or the index odd and the pp even, index - pp is odd. In other words index - pp[n] is even if even(index) == even(pp).

even_index = index % 2 == 0
even_index(1) == False
1-1(2) = 1 - pp[0] = False == True
1-2(2*8) = 1 - pp[1] = False == True
1-3(2*8*9) = 1 - pp[2] = False == True
1-4(2*8*9*21)= 1 - pp[3] = False == True

The results are:
1 = [False, False, False, False, False, False, False, False]
2 = [True, True, True, True, True, True, True]
3 = [False, False, False, False, False, False]
4 = [True, True, True, True, True]
5 = [False, False, False, False]
6 = [True, True, True]
7 = [False, False]
8 = [True]

Depending on the values we use, this is not always going to be the case. If all the numbers are odd we get something more interesting.

numbers = 3, 5, 7, 9, 11, 13, 15, 17
pp = [3, 30, 315, 3780, 51975, 810810, 14189175, 275675400]
even_pp = [False, True, False, True, False, True, False, True]
1 [True, False, True, False, True, False, True, False]
2 [True, False, True, False, True, False, True]
3 [True, False, True, False, True, False]
4 [True, False, True, False, True]
5 [True, False, True, False]
6 [True, False, True]
7 [True, False]
8 [True]

I used this code to compute the above:
def strange_even_func(numbers):
    even_pp = []
    pp = 1
    for i, a in enumerate(numbers):
        pp *= a
        even_pp.append(((i+1)*pp) % 2 == 0)
    result = []
    for i in range(len(numbers)):
        row = []
        even_index = (i % 2) != 0
        result.append(row)
        for j in range(i, len(numbers)):
            row.append(even_index == even_pp[j])
    return result

result = strange_even_func((3, 5, 7, 9, 11, 13, 15, 17))
for i, row in enumerate(result):
    print(i+1, row)
After looking at the results using various sets of numbers I noticed a pattern. All you have to do is compute the first row and consecutive rows are computed using shift and invert.
def strange_even_func(numbers):
    row = []
    pp = 1
    for i, a in enumerate(numbers):
        pp *= a
        row.append(((i+1)*pp) % 2 != 0)
    result = [row]
    while len(row) > 0:
        row = [not x for x in row[1:]]
        result.append(row)
    return result
            
result = strange_even_func((3, 5, 7, 9, 11, 13, 15, 17))
for i, row in enumerate(result):
    print(i+1, row)