login
List of permutations of 1,2,3,...,n for n=1,2,3,..., in lexicographic order.
43

%I #39 Mar 21 2022 11:48:39

%S 1,1,2,2,1,1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1,1,2,3,4,1,2,4,3,1,3,2,

%T 4,1,3,4,2,1,4,2,3,1,4,3,2,2,1,3,4,2,1,4,3,2,3,1,4,2,3,4,1,2,4,1,3,2,

%U 4,3,1,3,1,2,4,3,1,4,2,3,2,1,4,3,2,4,1,3,4,1,2,3,4,2,1,4,1,2,3,4,1,3,2,4,2

%N List of permutations of 1,2,3,...,n for n=1,2,3,..., in lexicographic order.

%C Contains every finite sequence of distinct numbers, infinitely many times.

%H Reinhard Zumkeller, <a href="/A030298/b030298.txt">Rows n=1..7 of triangle, flattened</a>

%H Daniel Forgues, Tilman Piesk, et al., <a href="https://oeis.org/wiki/Orderings">Orderings</a>, OEIS Wiki.

%H Antti Karttunen, <a href="http://oeis.org/wiki/Ranking_and_unranking_functions">Ranking and unranking functions</a>, OEIS Wiki.

%H <a href="/index/Per#perm">Index entries for sequences related to permutations</a>

%F Start with 1, then 12 and 21, then the 6 permutations of 123 in lexical order: 123, 132, 213, 231, 312, 321 and so on.

%e The permutations can be written as

%e 1,

%e 12, 21,

%e 123, 132, 213, 231, 312, 321, etc.

%e Write them in order and insert commas.

%t f[n_] := Permutations[Range@ n, {n}]; Array[f, 4] // Flatten (* _Robert G. Wilson v_, Dec 18 2012 *)

%o (Haskell)

%o import Data.List (permutations, sort)

%o a030298 n k = a030298_tabf !! (n-1) (k-1)

%o a030298_row = concat . sort . permutations . enumFromTo 1

%o a030298_tabf = map a030298_row [1..]

%o -- _Reinhard Zumkeller_, Mar 29 2012

%o (MIT/GNU Scheme, with _Antti Karttunen_'s intseq-library):

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

%o ;; Requires also A055089permvec from A055089.

%o (define (A030298 n) (vector-ref (A030298permvec (A084556 (A084557 n)) (A220660 (A084557 n))) (A220663 n)))

%o (define (A030298permvec size rank) (vector-reverse (vector1invert (A055089permvec size rank))))

%o (define (vector1invert vec) (make-initialized-vector (vector-length vec) (lambda (i) (1+ (- (vector-length vec) (vector-ref vec i))))))

%o (define (vector-reverse vec) (make-initialized-vector (vector-length vec) (lambda (i) (vector-ref vec (- (vector-length vec) i 1)))))

%o (Python)

%o from itertools import permutations, count, chain, islice

%o def A030298_gen(): # generator of terms

%o return chain.from_iterable(p for l in count(2) for p in permutations(range(1,l)))

%o A030298_list = list(islice(A030298_gen(),30)) # _Chai Wah Wu_, Mar 21 2022

%Y A030299 gives the initial portion of these same permutations as decimally encoded numbers.

%Y Cf. A098280, A098281, A030299, A170942.

%Y Cf. A001563 (row lengths), A001286 (row sums).

%Y Cf. A030496 for another ordering.

%Y The same information is essentially given in A055089, but in more compact way, by skipping those permutations which start with a fixed element (cf. A220696).

%Y A220660(n) tells the zero-based rank r of the n-th permutation in this sequence, among all finite permutations of the same size.

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

%Y A084557(n) tells that the n-th term a(n) belongs to the a(n):th lexicographically ordered permutation from the start (its "global rank").

%Y A220660(A084557(n)) tells the "local rank" of the permutation (amongst the permutations of the same size) to which the n-th term a(n) belongs.

%Y (A130664(n),A084555(n)) = (1,1),(2,3),(4,5),(6,8),(9,11),(12,14),... gives the starting and ending offsets of the n-th permutation in this list.

%K nonn,tabf

%O 1,3

%A _Clark Kimberling_

%E Entry revised by _N. J. A. Sloane_, Feb 02 2006

%E Keyword tabf added by _Reinhard Zumkeller_, Mar 29 2012