%I A055089
%S A055089 1,2,1,1,3,2,3,1,2,2,3,1,3,2,1,1,2,4,3,2,1,4,3,1,4,2,3,4,1,2,3,2,4,1,3,
%T A055089 4,2,1,3,1,3,4,2,3,1,4,2,1,4,3,2,4,1,3,2,3,4,1,2,4,3,1,2,2,3,4,1,3,2,4,
%U A055089 1,2,4,3,1,4,2,3,1,3,4,2,1,4,3,2,1,1,2,3,5,4,2,1,3,5,4,1,3,2,5,4,3,1,2
%N A055089 Canonical list of all finite permutations in reversed lexicographic ordering.
%F A055089 [seq(op(PermRevLexUnrank(j)), j=0..)]; (see Maple code given below).
%e A055089 In this table each row consists of A001563[n] permutations of (n+1) terms; 
               i.e. we have (1/) 2,1/ 1,3,2; 3,1,2; 2,3,1; 3,2,1/ 1,2,4,3; 2,1,4,
               3;
%e A055089 Append to each an infinite amount of fixed terms and we get a list of 
               rearrangements of natural numbers, but with only a finite number 
               of terms permuted:
%e A055089 1/2,3,4,5,6,7,8,9,...
%e A055089 2,1/3,4,5,6,7,8,9,...
%e A055089 1,3,2/4,5,6,7,8,9,...
%e A055089 3,1,2/4,5,6,7,8,9,...
%e A055089 2,3,1/4,5,6,7,8,9,...
%e A055089 3,2,1/4,5,6,7,8,9,...
%e A055089 1,2,4,3/5,6,7,8,9,...
%e A055089 2,1,4,3/5,6,7,8,9,...
%e A055089 Or alternatively, if we take only n first terms of each such infinite 
               row, then n! first rows give all permutations of the elements 1,2,
               ...,n.
%p A055089 factorial_base := proc(nn) local n,a,d,j,f; n := nn; if(0 = n) then RETURN([0]); 
               fi; a := []; f := 1; j := 2; while(n > 0) do d := floor(`mod`(n,(j*f))/
               f); a := [d,op(a)]; n := n - (d*f); f := j*f; j := j+1; od; RETURN(a); 
               end;
%p A055089 fexlist2permlist := proc(a) local n,b,j; n := nops(a); if(0 = n) then 
               RETURN([1]); fi; b := fexlist2permlist(cdr(a)); for j from 1 to n 
               do if(b[j] >= ((n+1)-a[1])) then b[j] := b[j]+1; fi; od; RETURN([op(b),
               (n+1)-a[1]]); end;
%p A055089 fac_base := n -> fac_base_aux(n,2); fac_base_aux := proc(n,i) if(0 = 
               n) then RETURN([]); else RETURN([op(fac_base_aux(floor(n/i),i+1)), 
               (n mod i)]); fi; end;
%p A055089 PermRevLexUnrank := n -> `if`((0 = n),[1],fexlist2permlist(fac_base(n)));
%p A055089 cdr := proc(l) if 0 = nops(l) then ([]) else (l[2..nops(l)]); fi; end; 
               # "the tail of the list"
%p A055089 # Same algorithm in different guise, showing how permutations are composed 
               of adjacent transpositions (compare to algorithm PermUnrank3R at 
               A060117):
%p A055089 PermRevLexUnrankAMSDaux := proc(n,r, pp) local s,p,k; p := pp; if(0 = 
               r) then RETURN(p); else s := floor(r/((n-1)!)); for k from n-s to 
               n-1 do p := permul(p,[[k,k+1]]); od; RETURN(PermRevLexUnrankAMSDaux(n-1, 
               r-(s*((n-1)!)), p)); fi; end;
%p A055089 PermRevLexUnrankAMSD := proc(r) local n; n := nops(factorial_base(r)); 
               convert(PermRevLexUnrankAMSDaux(n+1,r,[]),'permlist',1+(((r+2) mod 
               (r+1))*n)); end;
%Y A055089 Inversion vectors: A007623, cycle counts: A055090, minim. number of transpositions: 
               A055091, minim. number of adjacent transpositions: A034968, order 
               of each perm.: A055092, number of non-fixed elements: A055093, positions 
               of inverses: A056019, positions after Foata transform: A065181.
%Y A055089 Cf. A057112, A060112, A060117, A060118, A060132, A060133.
%Y A055089 Positions of fixed-point-free involutions: A064640.
%Y A055089 Sequence in context: A006843 A049456 A117506 this_sequence A060117 A112592 
               A070036
%Y A055089 Adjacent sequences: A055086 A055087 A055088 this_sequence A055090 A055091 
               A055092
%K A055089 nonn,tabf
%O A055089 0,2
%A A055089 Antti Karttunen Apr 18 2000