#!/usr/bin/python
__author__ = ‘DELL‘
class Node:
cakes = []
currentLevel = 0
steps = []
def inputCakes(cakes):
global n
global upperBound
n = int(raw_input(‘n:‘))
upperBound = 2 * n - 2
for i in range(0, n):
cakes.append(int(raw_input(str(i) + ‘:‘)))
def init():
global stack
node = Node()
inputCakes(node.cakes)
#node.cakes = swap(node.cakes, 1)
stack.append(node)
def swap(cakes, position):
newcakes = cakes[:]
for i in range(0, position / 2 + 1):
temp = newcakes[i]
newcakes[i] = newcakes[position - i]
newcakes[position - i] = temp
return newcakes
def isSorted(cakes):
for i in range(0, len(cakes) - 1):
if cakes[i] > cakes[i+1]:
return False
return True
def dfs():
global stack
global upperBound
global n
while len(stack) != 0:
node = stack[-1]
stack.pop()
if isSorted(node.cakes):
print ‘Found:‘, node.steps
if node.currentLevel < upperBound:
upperBound = node.currentLevel
else:
if node.currentLevel < upperBound:
for i in range(1, n):
if len(node.steps) == 0 or (len(node.steps) > 0 and i != node.steps[-1]):
childNode = Node()
childNode.cakes = swap(node.cakes, i)
childNode.currentLevel = node.currentLevel + 1
childNode.steps = node.steps[:]
childNode.steps.append(i)
stack.append(childNode)
n = 0
upperBound = 0
stack = []
if __name__ == ‘__main__‘:
init()
dfs()原文：http://blog.csdn.net/jarelzhou/article/details/19046135