describe
Given a positive integer N Represents the number of trains ,0<N<10, Next, enter the sequence of train arrivals , altogether N Trains , Each train in numbers 1-9 Number , There is only one way in and out of the railway station , At the same time, it stops in the train at the railway station , Only the late entrants exit , Only those who enter the first station can leave the station .
It is required to output the scheme of all trains leaving the station , Sort the output in dictionary order .
Input description ：
There are multiple sets of test cases , Enter a positive integer on the first line of each group N（0
Output description ：
Output the train departure serial number sorted from small to large in dictionary order , Each number is separated by a space , Wrap each output sequence , Specific view sample.
Example 1
Input ：
3
1 2 3
Copy
Output ：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
Copy
explain ：
First option ：1 Into the 、1 Out 、2 Into the 、2 Out 、3 Into the 、3 Out
Second option ：1 Into the 、1 Out 、2 Into the 、3 Into the 、3 Out 、2 Out
The third option ：1 Into the 、2 Into the 、2 Out 、1 Out 、3 Into the 、3 Out
The fourth option ：1 Into the 、2 Into the 、2 Out 、3 Into the 、3 Out 、1 Out
The fifth option ：1 Into the 、2 Into the 、3 Into the 、3 Out 、2 Out 、1 Out
Please note that ,[3,1,2] This sequence is impossible .
Code implementation ：
def func():
while True:
try:
n = int(input())
trains = input().strip().split(' ')
res = []
def rec_trains(cur_idx, in_trains, out_trains):
# If the last element of the original train list has entered the station , You can only exit at this time , Add the trains in the inbound list to the outbound trains in reverse order
if trains[-1] in in_trains:
res.append(' '.join(out_trains + in_trains[::-1]))
return
# If the inbound list is empty , You can only enter the station at this time , The arrival list plus the current train , The outbound list does not change
elif in_trains == []:
rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
# otherwise , It is possible to enter or leave the station
else:
# Departure , The current train index remains unchanged , Subtract the last element from the list of incoming trains , Outbound list plus inbound list the train that just left the station
rec_trains(cur_idx, in_trains[:-1], out_trains + [in_trains[-1]])
# Arrival , Current train index plus 1, The arrival list plus the current train , The outbound list does not change
rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
rec_trains(0, [], [])
res.sort()
print('\n'.join(res))
except:
break
if __name__ == '__main__':
func()
