cp's OEIS Frontend

A055089 List of all finite permutations in reversed colexicographic ordering.

%I A055089 #49 May 09 2020 00:35:31
%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,
%T A055089 3,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,
%U A055089 2,4,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 List of all finite permutations in reversed colexicographic ordering.
%H A055089 Antti Karttunen, <a href="/A055089/b055089.txt">Rows 0..719 of the irregular table, flattened.</a>
%H A055089 Daniel Forgues, Tilman Piesk, et al., <a href="https://oeis.org/wiki/Orderings">Orderings</a>, OEIS Wiki.
%H A055089 Antti Karttunen, <a href="http://oeis.org/wiki/Ranking_and_unranking_functions">Ranking and unranking functions</a>, OEIS Wiki.
%H A055089 Tilman Piesk, <a href="https://en.wikiversity.org/wiki/Permutations_and_partitions_in_the_OEIS">Permutations and partitions in the OEIS</a>, Wikiversity.
%H A055089 Lorenzo Sauras-Altuzarra, <a href="https://arxiv.org/abs/2002.03075">Some arithmetical problems that are obtained by analyzing proofs and infinite graphs</a>, arXiv:2002.03075 [math.NT], 2020.
%H A055089 <a href="/index/Fa#facbase">Index entries for sequences related to factorial base representation</a>
%H A055089 <a href="/index/Per#perm">Index entries for sequences related to permutations</a>
%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 number of fixed terms and we get a list of rearrangements of the 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 Alternatively, if we take only the first n terms of each such infinite row, then the first n! 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;
%t A055089 A055089L[n_] := Reverse@SortBy[DeleteCases[Permutations@Range@n, {__, n}], Reverse]; Flatten@Array[A055089L, 4] (* _JungHwan Min_, Aug 28 2016 *)
%o A055089 (MIT/GNU Scheme, with _Antti Karttunen_'s intseq-library):
%o A055089 ;; Note that in Scheme, vector indexing is zero-based.
%o A055089 (definec (A055089 n) (vector-ref (A055089permvec-short (A220658 n)) (A220659 n)))
%o A055089 (definec (A055089permvec-short rank) (A055089permvec  (+ 1 (A084558 rank)) rank))
%o A055089 (define (A055089permvec size rank) (let ((permvec (make-initialized-vector size 1+))) (let outloop ((rank rank) (i 2)) (cond ((zero? rank) (permvec1inverse-of permvec)) (else (let inloop ((k (- i 1))) (cond ((< k (- i (remainder rank i))) (outloop (floor->exact (/ rank i)) (+ 1 i))) (else (begin (let ((tmp (vector-ref permvec (- k 1)))) (vector-set! permvec (- k 1) (vector-ref permvec k)) (vector-set! permvec k tmp)) (inloop (- k 1)))))))))))
%o A055089 (define (permvec1inverse-of permvec) (make-initialized-vector (vector-length permvec) (lambda (i) (permvec1find-pos-of-i-from (+ 1 i) permvec))))
%o A055089 (define (permvec1find-pos-of-i-from i permvec) (let loop ((k 0)) (cond ((= k (vector-length permvec)) #f) ((= i (vector-ref permvec k)) (+ 1 k)) (else (loop (+ k 1)))))) ;; _Antti Karttunen_, Dec 18 2012
%Y A055089 Inversion vectors: A007623, cycle counts: A055090, minimum number of transpositions: A055091, minimum number of adjacent transpositions: A034968, order of each permutation: A055092, number of non-fixed elements: A055093, positions of inverses: A056019, positions after Foata transform: A065181; positions of fixed-point-free involutions: A064640.
%Y A055089 Cf. A057112, A060112, A060117, A060118, A060132, A060133.
%Y A055089 Cf. A195663, array of the infinite rows.
%Y A055089 This permutation list gives essentially the same information as A030298/A030299, but in a more compact way, by skipping those permutations of A030298 that start with a fixed element.
%Y A055089 A220658(n) gives the rank r of the permutation of which the term at a(n) is an element.
%Y A055089 A220659(n) gives the zero-based position (from the left) of that a(n) in that permutation of rank r.
%Y A055089 A084558(r)+1 gives the size of the finite subsequence (of the r-th infinite, but finitary permutation) which has been included in this list.
%K A055089 nonn,tabf
%O A055089 0,2
%A A055089 _Antti Karttunen_, Apr 18 2000
%E A055089 Name changed by _Tilman Piesk_, Feb 01 2012