|
|
A055089
|
|
List of all finite permutations in reversed colexicographic ordering.
|
|
71
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
Daniel Forgues, Tilman Piesk, et al., Orderings, OEIS Wiki.
|
|
FORMULA
|
[seq(op(PermRevLexUnrank(j)), j=0..)]; (see Maple code given below).
|
|
EXAMPLE
|
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; ... .
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:
1/2,3,4,5,6,7,8,9,...
2,1/3,4,5,6,7,8,9,...
1,3,2/4,5,6,7,8,9,...
3,1,2/4,5,6,7,8,9,...
2,3,1/4,5,6,7,8,9,...
3,2,1/4,5,6,7,8,9,...
1,2,4,3/5,6,7,8,9,...
2,1,4,3/5,6,7,8,9,...
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.
|
|
MAPLE
|
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;
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;
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;
PermRevLexUnrank := n -> `if`((0 = n), [1], fexlist2permlist(fac_base(n)));
cdr := proc(l) if 0 = nops(l) then ([]) else (l[2..nops(l)]); fi; end; # "the tail of the list"
# Same algorithm in different guise, showing how permutations are composed of adjacent transpositions (compare to algorithm PermUnrank3R at A060117):
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;
PermRevLexUnrankAMSD := proc(r) local n; n := nops(factorial_base(r)); convert(PermRevLexUnrankAMSDaux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end;
|
|
MATHEMATICA
|
A055089L[n_] := Reverse@SortBy[DeleteCases[Permutations@Range@n, {__, n}], Reverse]; Flatten@Array[A055089L, 4] (* JungHwan Min, Aug 28 2016 *)
|
|
PROG
|
;; Note that in Scheme, vector indexing is zero-based.
(definec (A055089permvec-short rank) (A055089permvec (+ 1 (A084558 rank)) rank))
(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)))))))))))
(define (permvec1inverse-of permvec) (make-initialized-vector (vector-length permvec) (lambda (i) (permvec1find-pos-of-i-from (+ 1 i) permvec))))
(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
|
|
CROSSREFS
|
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.
Cf. A195663, array of the infinite rows.
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.
A220658(n) gives the rank r of the permutation of which the term at a(n) is an element.
A220659(n) gives the zero-based position (from the left) of that a(n) in that permutation of rank r.
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.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|