How to determine the sum of a group of integers without using recursion

Question

This is my first Stack Overflow post and I hope it will be good.

This is a problem that I came up with myself, and now I'm a little ashamed to say, but it beats out the daylight from me. Please note that this is not homework, the honor of a scout.

In principle, the program accepts (as an input) a string consisting of integers from 0 to 9.

strInput = '2415043' 

Then you need to break this string of numbers into smaller groups of numbers, until, in the end, the sum of these groups gives you a predetermined amount. In the case of the above line, the target is 289.

 iTarget = 289 

In this example, there are two correct answers (but, most likely, only one will be displayed, since the program stops after reaching the goal):

 Answer 1 = 241, 5, 043 (241 + 5 + 043 = 289) 

Answer 2 = 241, 5, 0, 43 (241 + 5 + 0 + 43 = 289)

Note that integers do not change position. They are still in the same order as in the original line.

Now I know how to solve this problem using recursion. But the disappointing part is that I DON'T ALLOW to use recursion.

This needs to be solved using only while and for loops. . And obviously, lists and functions are fine.

Below is the code that I still have:

My code is:

  #Pre-defined input values, for the sake of simplicity lstInput = ['2','4','1','5','0','4','3'] #This is the kind of list the user will input sJoinedList = "".join(lstInput) #sJoinedList = '2415043' lstWorkingList = [] #All further calculuations are performed on lstWorkingList lstWorkingList.append(sJoinedList) #lstWorkingList = ['2415043'] iTarget = 289 #Target is pre-defined 

-

 def SumAll(_lst): #Adds up all the elements in a list iAnswer = 0 #Eg lstEg = [2,41,82] for r in _lst: # SumAll(lstEg) = 125 iAnswer += int(r) return(iAnswer) 

-

 def AddComma(_lst): #Adds 1 more comma to a list and resets all commas to start of list #Eg lstEg = [5,1001,300] (Note only 3 groups / 2 commas) # AddComma(lstEg) # [5,1,0,001300] (Now 4 groups / 3 commas) iNoOfCommas = len(_lst) - 1 #Current number of commas in list sResetString = "".join(_lst) #Make a string with all the elements in the list lstTemporaryList = [] sTemp = "" i = 0 while i < iNoOfCommas +1: sTemp += sResetString[i]+',' #Add a comma after every element i += 1 sTemp += sResetString[i:] lstTemporaryList = sTemp.split(',') #Split sTemp into a list, using ',' as a separator #Returns list in format ['2', '415043'] or ['2', '4', '15043'] return(lstTemporaryList) return(iAnswer) 

So basically, the pseudocode will look something like this:

Pseudo Code:

 while SumAll(lstWorkingList) != iTarget: #While Sum != 289 if(len(lstWorkingList[0]) == iMaxLength): #If max possible length of first element is reached AddComma(lstWorkingList) #then add a new comma / group and Reset(lstWorkingList) #reset all the commas to the beginning of the list to start again else: ShiftGroups() #Keep shifting the comma until all possible combinations #for this number of comma have been tried #Otherwise, Add another comma and repeat the whole process 

Phew! That was pretty much.

I worked out the process that the program will execute on a piece of paper, so the expected result is presented below:

OUTPUT:

 [2415043] #Element 0 has reached maximum size, so add another group #AddComma() #Reset() [2, 415043] #ShiftGroups() [24, 15043] #ShiftGroups() [241, 5043] #ShiftGroups() #...etc...etc... [241504, 3] #Element 0 has reached maximum size, so add another group #AddComma() #Reset() [2, 4, 15043] #ShiftGroups() [2, 41, 5043] #ShiftGroups() #etc...etc... [2, 41504, 3] #Tricky part 

Now here is the hard part. In the next step, the first element should be 24, and the other two should reset.

 #Increase Element 0 #All other elements Reset() [24, 1, 5043] #ShiftGroups() [24, 15, 043] #ShiftGroups() #...etc...etc [24, 1504, 3] #Increase Element 0 #All other elements Reset() [241, 5, 043] #BINGO!!!! 

Good. This is the main stream of program logic. Now the only thing I need to find out is how to make it work without recursion.

For those of you who have read up to this point, I sincerely thank you and hope that you still have the energy to help me solve this problem. If something is unclear, ask, and I will clarify (perhaps in the painful detail of XD).

Thanks again!

Edit: September 1, 2011

Thanks to everyone for the answer and for your answers. All of them are very good and, of course, more elegant than the route that I followed. However, my students have never worked with “import” or any data structures more advanced than lists. However, they know many functions of the list. I should also note that students are quite talented mathematically, many of them competed and placed in international mathematics competitions. Thus, this assignment does not go beyond their intellect; perhaps it goes beyond their knowledge of python.

I had Eureka last night! moment. I have not implemented it yet, but I will do it over the weekend, and then I will publish my results here. It may be a little rude, but I think he will do his job.

Sorry, it took me a long time to answer, my internet cap was reached, and I had to wait until the 1st for her to reset. Which reminds me, happy Spring of all (for those of you who are in the Southern Hemisphere).

Thanks again for your contributions. I will choose the top answer after the weekend. Hello!

Answer 1

A program that finds all the solutions can be elegantly expressed in a functional style.

Partitions

First write a function that breaks your string in every possible way. (The following implementation is based on http://code.activestate.com/recipes/576795/ .) Example:

 def partitions(iterable): 'Returns a list of all partitions of the parameter.' from itertools import chain, combinations s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable) n = len(s) first, middle, last = [0], range(1, n), [n] return [map(s.__getslice__, chain(first, div), chain(div, last)) for i in range(n) for div in combinations(middle, i)] 

Predicate

Now you will need to filter the list to find those sections that add to the desired value. So write a small function to check if a section meets this criterion:

 def pred(target): 'Returns a function that returns True iff the numbers in the partition sum to iTarget.' return lambda partition: target == sum(map(int, partition)) 

Main program

Finally, write the main program:

 strInput = '2415043' iTarget = 289 # Run through the list of partitions and find partitions that satisfy pred print filter(pred(iTarget), partitions(strInput)) 

Please note that the result is calculated in one line of code.

Result: [['241', '5', '043'], ['241', '5', '0', '43']]

Answer 2

Recursion is not the best tool to work in any case. itertools.product is.

Here's how I look for it:

Imagine the search space as all binary strings of length l, where l is the length of your string minus one.

Take one of these binary strings

Enter the numbers in the binary string between the numbers of your search string.

 2 4 1 5 0 4 3 1 0 1 0 1 0 

Turn 1 to a comma and 0 to nothing.

 2,4 1,5 0,4 3 

Add it all.

 2,4 1,5 0,4 3 = 136 

Is it 289? Nope. Try again with a different binary string.

 2 4 1 5 0 4 3 1 0 1 0 1 1 

You get the idea.

To the code!

 import itertools strInput = '2415043' intInput = map(int,strInput) correctOutput = 289 # Somewhat inelegant, but what the heck JOIN = 0 COMMA = 1 for combo in itertools.product((JOIN, COMMA), repeat = len(strInput) - 1): solution = [] # The first element is ALWAYS a new one. for command, character in zip((COMMA,) + combo, intInput): if command == JOIN: # Append the new digit to the end of the most recent entry newValue = (solution[-1] * 10) + character solution[-1] = newValue elif command == COMMA: # Create a new entry solution.append(character) else: # Should never happen raise Exception("Invalid command code: " + command) if sum(solution) == correctOutput: print solution 

EDIT: agf published another version of the code. It concatenates the string instead of my little hack, multiplying by 10 and adding an approach. In addition, it uses true and false instead of my JOIN and COMMA constants. I would say that both approaches are equally good, but of course I am biased. :)

 import itertools strInput = '2415043' correctOutput = 289 for combo in itertools.product((True, False), repeat = len(strInput) - 1): solution = [] for command, character in zip((False,) + combo, strInput): if command: solution[-1] += character else: solution.append(character) solution = [int(x) for x in solution] if sum(solution) == correctOutput: print solution 

Answer 3

To expand the pst hint, instead of just using the call stack as a recursion, you can create an explicit stack and use it to implement a recursive algorithm without actually calling anything recursive. Details left as an exercise for the student;)