import itertools
from timeit import default_timer as timer

def ist_sortiert(stapel):
	for i in range(1, len(stapel)):
		if stapel[i-1] < stapel[i]: return False
	return True

def umdrehen(stapel, index):
	unten = stapel[:index]
	oben = list(reversed(stapel[index:]))
	return unten + oben
	
def finde_beste_wendungen(stapel):	
	# Jeder Plinsenstapel lässt sich mit weniger als 2n Wendungen ordnen
	optimal_wendungen = [0] * (2*len(stapel)) 
	# Breitensuche
	warteschlange = [(stapel, [])]
	while warteschlange:
		stapel, wendungen = warteschlange[0]
		warteschlange.pop(0)
		if ist_sortiert(stapel):
			if len(wendungen) < len(optimal_wendungen):
				optimal_wendungen = wendungen
		else:
			if len(wendungen) + 1 < len(optimal_wendungen):
				for pos in range(len(stapel)-1):
					if not wendungen or pos != wendungen[-1]:
						neuer_stapel = umdrehen(stapel, pos)
						neue_wendungen = wendungen + [pos]
						warteschlange += [(neuer_stapel, neue_wendungen)]
	return optimal_wendungen

def erzeuge_stapel(n):
	return list(range(1,n+1))	

def maximale_anzahl_wendungen(n):
	maximum = 0
	for p in itertools.permutations(erzeuge_stapel(n)):
		stapel = list(p)
		einstichhöhen = finde_beste_wendungen(stapel)
		if maximum < len(einstichhöhen):
			maximum = len(einstichhöhen)
	return maximum	
	
def main():
	for n in range(0, 10):
		start = timer()
		max = maximale_anzahl_wendungen(n)
		end = timer()
		print(f'{n}\t{max}\t{end-start:.4} s')
	
if __name__ == '__main__':
	main()
