Как определить сумму группы целых чисел без использования рекурсии

Question

Это мой первый пост о переполнении стека, и я надеюсь, что он будет хорошим.

Это проблема, которую я сам придумал, и теперь мне немного стыдно говорить, но она выбивает из меня живые дневные света. Обратите внимание, что это не домашнее задание, честь разведчика.

Обычно программа принимает (в качестве входных данных) строку, составленную из целых чисел от 0 до 9.

strInput = '2415043'

Затем вам нужно разбить эту строку чисел на более мелкие группы чисел, пока в итоге сумма этих групп не даст вам заранее заданную сумму. В случае вышеупомянутой строки, цель - 289.

iTarget = 289

Для этого примера есть два правильных ответа (но, скорее всего, будет отображаться только один, так как программа остановится после достижения цели):

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

Ответ 2 = 241, 5, 0, 43 (241 + 5 + 0 + 43 = 289)

Обратите внимание, что целые числа не меняют положение. Они по-прежнему в том же порядке, в котором они были в исходной строке.

Теперь я знаю, как решить эту проблему с помощью рекурсии. Но расстраивает то, что мне НЕ разрешено использовать рекурсию.

Эту проблему необходимо решить, используя только циклы while и for. И, конечно же, списки и функции тоже в порядке.

Ниже приведен код, который у меня есть:

Мой код:

                                         #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             #E.g. 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
                                  #E.g. 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)

Так что в основном псевдокод будет выглядеть примерно так:

Псевдо-код:

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's until all possible combinations
                                              #for this number of comma's have been tried
                                              #Otherwise, Add another comma and repeat the whole process

Уф! Это было довольно круто.

Я прошел процесс, которому программа будет следовать на листе бумаги, поэтому ниже ожидаемый результат:

ВЫВОД:

[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

Теперь вот сложная часть. На следующем шаге первый элемент должен стать 24, а два других должны быть сброшены.

#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!!!!

Хорошо. Это основной поток логики программы. Теперь единственное, что мне нужно выяснить, это как заставить его работать без рекурсии.

Для тех из вас, кто читал до этого момента, я искренне благодарю вас и надеюсь, что у вас все еще есть энергия, чтобы помочь мне решить эту проблему. Если что-то неясно, пожалуйста, спросите, и я уточню (вероятно, в мучительной детали X-D).

Еще раз спасибо!

Редактировать: 1 сентября 2011

Спасибо всем за ответы и за ваши ответы. Все они очень хороши и определенно более элегантны, чем маршрут, которым я следовал. Однако мои ученики никогда не работали с «import» или какими-либо структурами данных, более продвинутыми, чем списки. Они, однако, знают довольно много функций списка. Я также должен отметить, что студенты математически одарены, многие из них соревновались и участвовали в международных математических олимпиадах. Так что это назначение не выходит за рамки их интеллект, возможно, только за пределами их знаний о питоне.

Прошлой ночью у меня была Эврика! момент. Я еще не реализовал это, но сделаю это в течение выходных, а затем опубликую свои результаты здесь. Это может быть несколько грубо, но я думаю, что это сделает работу.

Извините, мне потребовалось так много времени, чтобы ответить, моя интернет-кепка была достигнута, и мне пришлось ждать до 1-го, пока она не сбросилась. Что напоминает мне, счастливой весны всем (для тех из вас, кто в Южном полушарии).

Еще раз спасибо за ваш вклад. Я выберу лучший ответ после выходных. Привет!

Answer 1

Программа, которая находит все решения, может быть элегантно выражена в функциональном стиле.

Разделы

Сначала напишите функцию, которая разбивает вашу строку любым возможным способом.(Следующая реализация основана на http://code.activestate.com/recipes/576795/.) Пример:

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)]

Предикат

Теперь вам нужно отфильтровать список, чтобы найти те разделы, которые добавляются к желаемомузначение. Итак, напишите небольшую функцию, чтобы проверить, удовлетворяет ли раздел этому критерию:

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))

Основная программа

Наконец, напишите основную программу:

strInput = '2415043'
iTarget = 289

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

Примечаниечто результат вычисляется в одной строке кода.

Результат: [['241', '5', '043'], ['241', '5', '0', '43']]

Answer 2

Рекурсия не лучший инструмент для работы в любом случае. itertools.product есть.

Вот как я его ищу:

Представьте пространство поиска как все двоичные строки длины l, где l - длина вашей строки минус один.

Возьмите одну из этих двоичных строк

Запишите числа в двоичной строке между номерами строки поиска.

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

Превратите 1 в запятые, а 0 - в ничто.

2,4 1,5 0,4 3

Добавьте все это.

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

Это 289? Нету. Попробуйте еще раз с другой двоичной строкой.

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

Вы поняли идею.

На код!

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 выложил еще одну версию кода. Он объединяет строку вместо моего несколько хакерского умножения на 10 и добавления подхода. Кроме того, он использует true и false вместо моих констант JOIN и COMMA. Я бы сказал, что эти два подхода одинаково хороши, но я, конечно, предвзят, что у меня 1029. :)

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

Чтобы расширить подсказку pst, вместо того, чтобы просто использовать стек вызовов, как это делает рекурсия, вы можете создать явный стек и использовать его для реализации рекурсивного алгоритма, фактически не вызывая ничего рекурсивного.Детали оставлены в качестве упражнения для студента;)