3
\$\begingroup\$

This function is checking, whether it has enough money in a list called self.deviceMoney to make change.

It works exactly the way I want, but only in case where not many coins are in self.deviceMoney. The algorithm is checking, if the list has enough coins to create some number, if yes remove that many coins from list.

Example

Number = 8
self.deviceMoney=[1,3,4,5,2]

Now, we can create this number from [3,4,1] or [5,3] etc.

List after operation self.deviceMoney == [5,2]

When I put into this list for example 200 coins, my program stops responding. I think, because a large amount of itertools.combinations. How can I optimize this function or resolve this problem to make the algorithm much better?

def changeOperation(self):
    self.deviceMoney.sort()
    tmpChange=int(self.change*100)
    tmp=set()
   # print(self.change)
    print(self.deviceMoney)

    if self.change > 0:
        for i in range(1,len(self.deviceMoney)):
            for j in itertools.combinations(self.deviceMoney,i):
                if sum(j) == tmpChange:
                    tmp.add(tuple(j))
                    print("tmp.append(list(j)): " +str(tmp))

        if tmp:
            a = next(iter(tmp))
            print("a: " + str(a))
            print("a[0]= ",a[0])
            for k in range(len(a)):
                self.deviceMoney.remove(a[k])

            print("deviceMoney: "+str(self.deviceMoney))

            self.errorMessageBox("some string"))
        else:
            self.errorMessageBox("some string")
            self.deviceMoney=[]

    elif self.change == 0:
        self.errorMessageBox("some string")

    else:
        pass

 #prints for tests
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You create all the possible combinations and then you just use the first one. Seems you could just calculate the first one. But there's one possibly bigger issue which I guess is not really what it seems: If no combination was found, you "empty" the deviceMoney list (more specifically you assign a new empty list to self.deviceMoney). \$\endgroup\$
    – kyrill
    May 4, 2017 at 18:08
  • 1
    \$\begingroup\$ You should check out this SO question. That might help \$\endgroup\$
    – smac89
    May 4, 2017 at 18:09

0

Your Answer

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