cp's OEIS Frontend

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

%I A030298 #43 Jan 14 2025 14:45:56
%S A030298 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 A030298 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 A030298 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 A030298 List of permutations of 1,2,3,...,n for n=1,2,3,..., in lexicographic order.
%C A030298 Contains every finite sequence of distinct numbers, infinitely many times.
%H A030298 Reinhard Zumkeller, <a href="/A030298/b030298.txt">Rows n=1..7 of triangle, flattened</a>
%H A030298 Daniel Forgues, Tilman Piesk, et al., <a href="https://oeis.org/wiki/Orderings">Orderings</a>, OEIS Wiki.
%H A030298 Antti Karttunen, <a href="http://oeis.org/wiki/Ranking_and_unranking_functions">Ranking and unranking functions</a>, OEIS Wiki.
%H A030298 <a href="/index/Per#perm">Index entries for sequences related to permutations</a>
%F A030298 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 A030298 The permutations can be written as
%e A030298   1,
%e A030298   12, 21,
%e A030298   123, 132, 213, 231, 312, 321, etc.
%e A030298 Write them in order and insert commas.
%t A030298 f[n_] := Permutations[Range@ n, {n}]; Array[f, 4] // Flatten (* _Robert G. Wilson v_, Dec 18 2012 *)
%o A030298 (Haskell)
%o A030298 import Data.List (permutations, sort)
%o A030298 a030298 n k = a030298_tabf !! (n-1) (k-1)
%o A030298 a030298_row = concat . sort . permutations . enumFromTo 1
%o A030298 a030298_tabf = map a030298_row [1..]
%o A030298 -- _Reinhard Zumkeller_, Mar 29 2012
%o A030298 (MIT/GNU Scheme, with _Antti Karttunen_'s intseq-library):
%o A030298 ;; Note that in Scheme, vector indexing is zero-based.
%o A030298 ;; Requires also A055089permvec from A055089.
%o A030298 (define (A030298 n) (vector-ref (A030298permvec (A084556 (A084557 n)) (A220660 (A084557 n))) (A220663 n)))
%o A030298 (define (A030298permvec size rank) (vector-reverse (vector1invert (A055089permvec size rank))))
%o A030298 (define (vector1invert vec) (make-initialized-vector (vector-length vec) (lambda (i) (1+ (- (vector-length vec) (vector-ref vec i))))))
%o A030298 (define (vector-reverse vec) (make-initialized-vector (vector-length vec) (lambda (i) (vector-ref vec (- (vector-length vec) i 1)))))
%o A030298 (Python)
%o A030298 from itertools import permutations, count, chain, islice
%o A030298 def A030298_gen(): # generator of terms
%o A030298     return chain.from_iterable(p for l in count(2) for p in permutations(range(1,l)))
%o A030298 A030298_list = list(islice(A030298_gen(),30)) # _Chai Wah Wu_, Mar 21 2022
%Y A030298 A030299 gives the initial portion of these same permutations as decimally encoded numbers.
%Y A030298 Cf. A098280, A098281, A030299, A170942.
%Y A030298 Cf. A001563 (row lengths), A001286 (row sums).
%Y A030298 Cf. A030496 for another ordering.
%Y A030298 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 A030298 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 A030298 A220663(n) tells the zero-based position (from the left) of that a(n) in that permutation of rank r.
%Y A030298 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 A030298 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 A030298 (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 A030298 nonn,tabf
%O A030298 1,3
%A A030298 _Clark Kimberling_
%E A030298 Entry revised by _N. J. A. Sloane_, Feb 02 2006
%E A030298 Keyword tabf added by _Reinhard Zumkeller_, Mar 29 2012