CODEWITHSUNDEEP
python
Cheetah jimi
Cheetah jimi

Reputation: 31

output repetition

I wrote this program which outputs pythagorean triplet whose sum is a certain number(this would be the parameter). The program runs perfectly but the same triplet is appearing multiple times and I want one triplet to appear just once. I was wondering if someone could help me out. Thanks!

def pythagoreanCheck(tripletList):
    '''
        Checks whether the three numbers are pythagorean triplet
        returns True or False
    '''

    trip_list = [0,1,2]

    if tripletList[0]**2 + tripletList[1]**2 == tripletList[2]**2:
        return True
    else:
        return False

def givMeSum(target):
    '''
        returns 3 numbers such that their sum is equal to target
    '''       

    listOfa = xrange(1,target)
    listOfb = xrange(1,target)
    listOfc = xrange(1,target)

    for i in listOfa:
        for j in listOfb:
            for k in listOfc:
                add = i + j + k

                if add == target:
                    add_list = [i,j,k]
                    add_list.sort()

                    value = pythagoreanCheck(add_list)

                    if value:
                        print add_list


def main():
    givMeSum(12)

main()

Upvotes: 1

Views: 106

Answers (3)

Eric
Eric

Reputation: 97601

You need to make sure that i <= j <= k:

def pythagoreanCheck(tripletList):
    '''
        Checks whether the three numbers are pythagorean triplet
        returns True or False
    '''
    a, b, c = tripletList
    return a**2 + b**2 == c**2

def givMeSum(target):
    '''
        returns 3 numbers such that their sum is equal to target
    '''       

    for i in xrange(1, target):
        for j in xrange(i, target):      # j >= i
            for k in xrange(j, target):  # k >= j   
                if i + j + k == target:
                    add_list = [i, j, k]  # no need to sort any more

                    if pythagoreanCheck(add_list):
                        print add_list


def main():
    givMeSum(12)

main()

As noted, this algorithm is far from optimal, but this will at least solve the problem you're seeing.

Here's a slightly better way (two nested loops instead of three):

def giveMeSum(target):
    '''
        returns 3 numbers such that their sum is equal to target
    '''    
    for i in xrange(1, target):
        for j in xrange(i, target):
            k = target - i - j
            if k < j:
                break  # skip to the next value of i - all remaining js are too big

            add_list = [i, j, k]

            if pythagoreanCheck(add_list):
                print add_list

Upvotes: 0

Siddharth Toshniwal
Siddharth Toshniwal

Reputation: 159

  1. Consider storing each tuple in a hash table (dictionary)instead of printing it within the innermost loop. At the end of all the loops completion, print all the values in the hash.

  2. Aside from your question, you can make the algo faster by creating a hash of integers and replace the innermost loop with a hash search.

Upvotes: 0

kdazzle
kdazzle

Reputation: 4300

It's because you're doing your calculations in a nested list and then creating a sorted list of 3 different permutations of the same numbers.

Since i, j, and k will enter different combinations of the same three numbers 3 times, add will equal target each time, which means that add_list is created and sorted 3 times. Which means that it will create the same list 3 times.

I think that you should just take out 

add_list.sort()

And Siddharth is right, your algorithm is really inefficient. You're turning it into an O(n^3) algorithm, which could take a really long time with larger target numbers.

Upvotes: 1

Related Questions