在 python 的回溯中传递列表（堆栈）

Question

我正尝试在 python 中编码 this problem 的 hackerrank。

（如果link不工作，问题如下）

"悟空用一些方块写了一条秘密信息。每个方块包含一个字符。悟饭喜欢玩这些积木。他把这些积木一层一层地堆起来。

在任何时候，Gohan 都可以将一个块从秘密消息的前面移到堆栈的顶部，或者他可以从顶部移除该块并将其添加到他所发送的新消息的末尾已创建。

Gohan 通过将他从堆栈顶部移除的块按照从堆栈顶部移除的顺序添加到新字符串的末尾来创建此新消息。

最终消息的字符数与原始消息的字符数相同，即所有块都必须从堆栈中移除。悟空担心他原来的信息可能会丢失。

他想知道 Gohan 可以用多少种方式重新创建原始消息以及 Gohan 可以创建的不同消息的数量。

示例输入：球

示例输出：2 9 "

Gohan 可以创建以下 9 条消息：{llab, lalb, labl, allb, albl, abll, blla, blal, ball}

这是一个回溯问题，需要递归传递一个栈，递归修改(insert/delete)栈。我正在使用普通列表作为堆栈。

问题的编辑是：(link)

（如果link不起作用，社论在下面）

Times_Recreated=0
Distinct_Messages=0

calculate_ans(OriginalMessage,Index,Stack st,NewMessage)

if Index = Length of the original message
        Pop the remaining characters in the stack and add them to NewMessage
        If NewMessage hasn't been encountered already, increment Distinct_Messages.
        If NewMessage is same as OriginalMessage, increment Times_Recreated.
        Return

Add OriginalMessage[Index] to the stack
Recurse for the remaining string  calculate_ans(OriginalMessage,Index+1,st,NewMessage)

Pop the character from the top of the stack to restore the original state

If the stack isn't empty
    Pop a character from the stack and add the character to NewMessage
    Recurse calculate_ans(OriginalMessage,Index,st,NewMessage)

我正在尝试下面的代码，但我无法将列表（堆栈）传递给允许其修改的递归。

我认为这个列表是函数的全局列表。它显示错误 - IndexError：从空列表中弹出

s= str(raw_input()) #string s as message input
words= set() # to store distinct messages Gohan can create
count=0 # number of ways in which Gohan could have recreated the original message

# s=message, i=index of s to be processed, stack= list as stack, new_s= new message 
def backtrack(s, i, stack, new_s):
    if i==len(s): 
        # pop the remaining characters from stack and add them to new_message 
        while stack:
            new_s=new_s+ stack.pop() 
        words.add(new_s) # insert new message to set words 
        if new_s==s:
            count+=1 # increase count if original message is obtained 
        return
    stack.append(s[i]) #push in stack 
    backtrack(s, i+1, stack, new_s) # backtrack 
    stack.pop() #pop from stack 
    if stack:
        new_s= new_s+stack.pop() # new message by appending stack pop 
        backtrack(s, i, stack, new_s) # backtrack 


# function call with i=0, a blank list stack and empty new message new_s
backtrack(s, 0, [], "") 
print count, len(words)  # printing output

请更正此代码或提供一些 method/code 以在这种情况下通过列表。

Answer 1

python 中的变量通过引用传递，这意味着当您对堆栈变量进行递归调用并弹出其所有元素时，它在每个其他递归调用中都是空的，因此将其更改为

backtrack(s, i+1, [x for x in stack], new_s)

每次都会创建一个新列表，并且在回溯函数中将计数声明为全局变量

global count

在 python 的回溯中传递列表（堆栈）

Passing list (stack) in backtracing in python

python

recursion

stack

list

backtracking