login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055089 List of all finite permutations in reversed colexicographic ordering. 56
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

A. Karttunen, Rows 0..719 of the irregular table, flattened.

Daniel Forgues, Tilman Piesk, et al, Orderings, OEIS Wiki.

A. Karttunen, Ranking and unranking functions, OEIS Wiki.

Index entries for sequences related to permutations

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 amount of fixed terms and we get a list of rearrangements of 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,...

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.

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;

PROG

(MIT/GNU Scheme, with Antti Karttunen's intseq-library):

;; Note that in Scheme, vector indexing is zero-based.

(definec (A055089 n) (vector-ref (A055089permvec-short (A220658 n)) (A220659 n)))

(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, 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. Positions of fixed-point-free involutions: A064640.

Cf. A057112, A060112, A060117, A060118, A060132, A060133.

Cf. A195663, array of the infinite rows.

This permutation list gives essentially the same information as A030298/A030299, but in more compact way, by skipping those permutations of A030298 which start with a fixed element.

A220658(n) tells the rank r of permutation which term at a(n) is element of.

A220659(n) tells the zero-based position (from the left) of that a(n) in that permutation of rank r.

A084558(r)+1 tells the size of the finite subsequence (of the r:th infinite, but finitary permutation) which has been included in this list.

Sequence in context: A049456 A117506 A179205 * A060117 A196526 A234504

Adjacent sequences:  A055086 A055087 A055088 * A055090 A055091 A055092

KEYWORD

nonn,tabf

AUTHOR

Antti Karttunen, Apr 18 2000

EXTENSIONS

Name changed by Tilman Piesk, Feb 01 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 19 00:07 EDT 2014. Contains 240735 sequences.