Home > OS >  Fastest way of going through many arrays
Fastest way of going through many arrays

Time:09-19

In python, I am trying to check all possible combinations of a5 b5 c5 d5 = e5
I am starting my search with numbers under 200, but it takes a huge amount of time to go through all possibilities, how could I make this code faster?

xL = [x*x*x*x*x for x in range(1, 200)]
for x1 in xL:
    for x2 in xL:
        for x3 in xL:
            for x4 in xL:
                for x5 in xL:
                    if x1   x2   x3   x4 == x5:
                        print(x1, x2, x3, x4, x5)

CodePudding user response:

WARNING: I'm not a python programmer and none of the example code is tested. Expect bugs and silly syntax errors. Focus on the concepts.

If a5 b5 c5 d5 = e5 then you can rearrange the formula to get a5 = e5 - b5 - c5 - d5

If the minimum values for b, c and d is 1; then you also know that a5 <= e5 - 1 - 1 - 1

In other words, after you've chosen a value for e, you can limit the range of values of a5 to the range 1 to e5 - 3; like maybe:

xL = [x*x*x*x*x for x in range(1, 200)]
for e5 in xL:
    for a5 in xL:
        if a5 > e5 - 3: break

You can rearrange the formula again to get b5 = e5 - a5 - c5 - d5. If the minimum values for c and d is 1; then you also know that b5 <= e5 - a5 - 1 - 1.

In other words, after you've chosen a value for e and chosen a value for a, you can limit the range of values of b5 to the range 1 to e5 - a5 - 2; like maybe:

xL = [x*x*x*x*x for x in range(1, 200)]
for e5 in xL:
    for a5 in xL:
        if a5 > e5 - 3: break
        for b5 in xL:
            if b5 > e5 - a5 - 2: break

If you continue this logic you end up with:

xL = [x*x*x*x*x for x in range(1, 200)]
for e5 in xL:
    for a5 in xL:
        if a5 > e5 - 3: break
        for b5 in xL:
            if b5 > e5 - a5 - 2: break
            for c5 in xL:
                if c5 > e5 - a5 - b5 - 1: break
                for d5 in xL:
                    if d5 > e5 - a5 - b5 - c5: break
                    if a5   b5   c5   d5 == e5:
                        print(e5, a5, b5, c5, d5)
                        break

However; after you've found one solution you can merely swap the values in a and b to find another solution. For example, you might be able to do this:

                    if a5   b5   c5   d5 == e5:
                        print(e5, a5, b5, c5, d5)
                        print(e5, b5, a5, c5, d5)
                        break

The problem is that the same solution will be reported twice, unless you can find a way to avoid it. You can avoid that by making sure that b is never larger than a and doing this:

xL = [x*x*x*x*x for x in range(1, 200)]
for e5 in xL:
    for a5 in xL:
        if a5 > e5 - 3: break
        for b5 in xL:
            if b5 > a5: break
            if b5 > e5 - a5 - 2: break
            for c5 in xL:
                if c5 > e5 - a5 - b5 - 1: break
                for d5 in xL:
                    if d5 > e5 - a5 - b5 - c5: break
                    if a5   b5   c5   d5 == e5:
                        print(e5, a5, b5, c5, d5)
                        if a5 != b5:
                            print(e5, b5, a5, c5, d5)
                        break

This is "very fortunate" because that if b5 > a5: break will improve performance a lot.

However; after you've found "one solution that becomes 2 solutions" you can merely swap the values in a and c to find another solution, and also swap the values in b and c to find another solution; using the same technique to avoid reporting the same solution twice (and improving performance more).

xL = [x*x*x*x*x for x in range(1, 200)]
for e5 in xL:
    for a5 in xL:
        if a5 > e5 - 3: break
        for b5 in xL:
            if b5 > a5: break
            if b5 > e5 - a5 - 2: break
            for c5 in xL:
                if c5 > b5: break
                if c5 > e5 - a5 - b5 - 1: break
                for d5 in xL:
                    if d5 > e5 - a5 - b5 - c5: break
                    if a5   b5   c5   d5 == e5:
                        print(e5, a5, b5, c5, d5)
                        if a5 != b5:
                            print(e5, b5, a5, c5, d5)
                            if b5 != c5:
                                print(e5, c5, a5, b5, d5)
                        else:
                            if b5 != c5:
                                print(e5, a5, c5, b5, d5)
                        if a5 != c5:
                            print(e5, c5, b5, a5, d5)
                        break

However; after you've found "one solution that becomes several solutions" you can merely swap the values in a and d to find another solution, and also swap the values in b and d to find another solution, and also swap the value in c and d to find another solution; using the same technique to avoid reporting the same solution twice (and improving performance more).

  • Related