## Help Pls!!!How to make this code efficient?

A forum for general discussion of the Python programming language.

### Help Pls!!!How to make this code efficient?

Here is my code.This is a solution for one of my sums.But the issue is the running time of this code.

Code: Select all
`def o(s):    l=len(s)    return len(set([a+b+c for a in s for b in s for c in s]))==l*(l+1)*(l+2)//6M=int(input())N=3**Mi=1s=M*[i]while i:    if s[i]-N:        s[i]=s[i]+1        if o(s[:i+1]):            if i<M-1:                i=i+1                s[i]=s[i-1]            else:                N=s[-1]    else:        i=i-1print(N)`

1<input<12

When I give inputs such as 2,3,4, the running time is ok.But when we use inputs like 6,7 it is taking too much time.So how can I improve this?
Last edited by Mekire on Sat Oct 26, 2013 10:22 am, edited 1 time in total.
Reason: Locked. Fixed indentation. Please describe the goal.
KillerCode

Posts: 3
Joined: Sat Oct 26, 2013 9:32 am

### Re: Help Pls!!!How to make this code efficient?

i have no idea what your code does. I also see code that looks just plain old odd to me:
Code: Select all
`        return len(set([a+b+c                        for a in s for b in s for c in s])                   )==l*(l+1)*(l+2)//6`

Your code is so convoluted, i am not even going to trry to make sense of it. The fact that you put unmeaningful variable names makes it that much harder.

However, have you made a counter for your while loop and seen how many loops it goes for each number?
for my computer:
for 4:
it loops 200+ times

for 5:
it loops 5000+ times

for 6:
it loops 211,611 times

for 7:
i stopped it at 4+ million loops, as i figured i am not going to wait for the pattern to end what sure is awhile.

I would bet its safe to assume if you trace this back to its source problem that you would find the culprit
we will be moving to python-forum.io on October 1 2016
more details here

metulburr

Posts: 2244
Joined: Thu Feb 07, 2013 4:47 pm
Location: Elmira, NY

### Re: Help Pls!!!How to make this code efficient?

Would you mind explaining what the program is supposed to do? Explain your end goal; not the method you have chosen.

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Help Pls!!!How to make this code efficient?

Looks like he's trying to brute-force a project euler problem(or something similar).
That's not likely to work.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1790
Joined: Thu Feb 07, 2013 3:42 pm

### Re: Help Pls!!!How to make this code efficient?

Here is how it works.

For example, consider the function o. It takes a collection of numbers, s (with length l), iterates over all triples a, b, c of three elements from s (with repetition), counts the number of distinct sums a + b + c, and returns True if the number of distinct sums is equal to (l+2)-choose-3.

So for example, if you call o([2, 3, 4]) then the set of distinct sums will be

{2+2+2 = 6, 2+2+3 = 7, 2+2+4 = 8, 2+3+4 = 9, 2+4+4 = 10, 3+4+4 = 11, 4+4+4 = 12}

which has length 7, but (l+2)-choose-3 is 10, so o([2, 3, 4]) returns False.

So can you help me now?
KillerCode

Posts: 3
Joined: Sat Oct 26, 2013 9:32 am

### Re: Help Pls!!!How to make this code efficient?

You still seem to be describing your chosen implementation. What exactly is the original problem?

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Help Pls!!!How to make this code efficient?

I don't get what (l+2)-choose-3 means, but you can do something along these lines
Code: Select all
`>>> import itertools>>> my_list = [2,3,4,5,6,7,8,9,10,12]>>> distinct_sums = set(sum(perm) for perm in itertools.permutations(my_list, 5))>>> len(distinct_sums), distinct_sums(27, set([20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]))`
hrs

Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

### Re: Help Pls!!!How to make this code efficient?

Except that itertools.permutations lacks repetition. Instead you could use itertools.product(my_list, repeat=3).
hrs

Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

### Re: Help Pls!!!How to make this code efficient?

Code: Select all
`itertools.combinations_with_replacement(s,3)`

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona