在python中的回溯中传递列表(堆栈)

Question

我正在尝试用python编写这个hackerlink问题。

（如果链接不工作，问题在下面）

"悟空用一些方块写了一条秘密信息。每个方块都包含一个字符。Gohan喜欢玩这些积木。他把这些积木叠在一起。

在任何时间点，Gohan都可以将一个块从秘密消息的前面移动到堆栈的顶部，也可以从顶部移除该块并将其添加到他创建的新消息的末尾。

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

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

他想知道Gohan可以通过多种方式重新创建原始信息，以及Gohan可以创建的不同信息的数量。

样本输入：球

样品输出：2 9"

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

这是一个回溯问题，我们需要在递归中传递堆栈，而在递归中修改（插入/删除）堆栈。我使用普通列表作为堆栈。

问题的社论是：（链接）

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

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 

在这种情况下，请更正此代码或提供一些方法/代码来传递列表。

Answer 1

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

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

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

global count