program LEX1 (output);
   const n=...;   {n порядок перестановок}
   var p : array [1..n] of 1..n;
         i,r : 1..n;
   procedure INVERT (m : integer); {инвертирование p[m]...p[n] }
       var i,j: 1..n;
       begin i:=m; j:=n;
           while i<j do begin r:=p[i]; p[i]:=p[j]; p[j]:=r;
                                        i:=i+1; j:=j-1
                               end
       end {INVERT};
 procedure Lec (k:integer); 
   var i : 1..n;
   begin 
      if  k=n then 
  {1}              begin for  i:=1 to n do write (p[i]); writeln end
                else
                     for  i:=n downto k do 
   {2}                begin 
                            LEC (k+1);
                            if i>k then
                                        begin 
                                          r:=p[i]; p[i]:=p[k]; p[k]:=r;
   {3}                                  INVERT (k+1)
   {4}                               end
                        end
  end {LEC};
 begin 
    for i:=1 to n do p[i]:=i;
    LEC (1)
 end.

def print_permutations_recursive(n):
	def step(tail_start):
		# if the tail has just one element, print what we've got
		if tail_start == n - 1:
			print p
			return
		# try all possible selections of n elements from a total of (n+1)
		for to_swap in xrange(tail_start + 1, n):
			step(tail_start + 1) # now the tail is reversed
			p[tail_start+1:] = reversed(p[tail_start+1:]) # undoing that
			p[to_swap], p[tail_start] = p[tail_start], p[to_swap]
		step(tail_start + 1) # not reversing after the last time
	p = range(1, n + 1)
	step(0)