[Question]
  [
The goal of this challenge is to take a positive integer `n` and output (in lexicographic order) all sequences \$S = [a\_1, a\_2, ..., a\_t]\$ of distinct positive integers such that \$\max(S) = n\$.
For example, for an input `n = 3` your program should output the following eleven sequences in the following order:
```
[
  [1, 2, 3],
  [1, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3],
  [2, 3, 1],
  [3],
  [3, 1],
  [3, 1, 2],
  [3, 2],
  [3, 2, 1],
]
```
(In general, for an input `n`, your program should output [\$A001339(n-1)\$](https://oeis.org/A001339) sequences.)
---
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") challenge, so the shortest code wins.
  
[Answer]
# [Python 2](https://docs.python.org/2/), 78 bytes
```
f=lambda n,l=[]:sum([f(n,l+[i+1])for i in range(n)if~-(i+1in l)],[l]*(n in l))
```
[Try it online!](https://tio.run/##HcmxDkAwEIDhV7nxjhqwSTxJ06HCcUmdphgsXr0a4/f/8bm2Q7uceQx@n2YPasJo3XDeO1rGotpK3TriI4GAKCSv64JKwm@DZZUUyBkbXIUKvyjHJHoBY0/5Aw "Python 2 – Try It Online")
Python 3 lets us save some bytes with set unpacking.
**[Python 3](https://docs.python.org/3/), 74 bytes**
```
f=lambda n,l=[]:sum([f(n,l+[i])for i in{*range(1,n+1)}-{*l}],[l]*(n in l))
```
[Try it online!](https://tio.run/##DclNCoAgEEDhq7gcf1qEu6CTiAujLGGcxGwR4tnN3ft46SvXTbp3v6KL2@4YKVyNXZ43gvEwJE2w3N@ZBRaoiuzoPGBWJGfepiqwWWXQCqCxGXLeUw5UwIMe/QM "Python 3 – Try It Online")
[Answer]
# [Husk](https://github.com/barbuz/Husk), 9 bytes
```
Of€¹umu´π
```
[Try it online!](https://tio.run/##yygtzv7/3z/tUdOaQztLc0sPbTnf8P//f2MA "Husk – Try It Online")
### Explanation
```
Of€¹umu´π
       ´π     All length n combinations of 1..n
     mu       Get the unique values of each list
    u         Get the unique lists
 f€¹          Filter by those that contain n
O             And sort lexographically
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 10 bytes
```
{⟦₆⊇,?p}ᶠo
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r/v/rR/GWPmtoedbXr2BfUPty2IP//f@P/UQA "Brachylog – Try It Online")
* `{…}ᶠo`: order all results of:
* `⟦₆`: from `[1,2,…,N-1]`
* `⊇`: try a subset (e.g. `[1,2]` then `[2]` then `[1]` then `[]`)
* `,?`: append the input `[1,2,3]`
* `p`: permute the list
[Answer]
# [Haskell](https://www.haskell.org/), 60 bytes
```
n!b=[[]|all(<n)b]++[k:c|k<-b,c<-n!filter(/=k)b]
f n=n![1..n]
```
[Try it online!](https://tio.run/##DcmxCoAgEADQva84ocEojWgL/RJxUFESryPK0X@33vpO95aI2Dsxr42xzSFyRZO382zKEVpRwi9BCWIpY40PX3X5d0hAmpjZpCTbL5cJNNxPpgojJNj7Bw "Haskell – Try It Online")
Very much like xnor's Python approach, but my `b` is the complement of their `l`.
## Explanation
Definition: an `n`-SDPI is a sequence of distinct positive integers `1 ≤ i ≤ n`, among which is `n`.
We can think about "using up" numbers as we write such a sequence: if `n=5` and we start by writing down a `2`, only `[1,3,4,5]` are left at our disposal (we can't reuse 2).
`n!b` computes all of the *continuations* of an `n`-SDPI where we have only the numbers in `b` left at our disposal. Let's call `b` our "bag" of numbers that could still go in the sequence.
For example: `4![1,3]` returns all the ways we can continue if we've already written down a 2 and a 4 (in some order), and we have a `1` and a `3` left in our bag.
Which continuations are there?
Either we stop here (yielding `[]`), or we turn to our bag (yielding some non-empty continuations).
1. If `n` is no longer in our bag (`all(<n)b`), then we've made a valid n-SDPI, so we're happy ending the list here and yield `[]` as a possible continuation.
2. Furthermore, for every `k` in our bag, we can place `k`, followed by every continuation `c` from `n!filter(/=k)b` (removing `k` from the bag).
Since `b` is always sorted, and we yield `[]` before non-empty lists, the result is also lexicographically sorted.
Finally, `f` asks which `n`-SDPIs we can make with a full bag (`[1..n]`).
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~10~~ ~~9~~ ~~8~~ 7 bytes
```
œ!RẎṢiƇ
```
[Try it online!](https://tio.run/##y0rNyan8///oZMWgh7v6Hu5clHms/f/hdvf//40B "Jelly – Try It Online")
-1 byte [thanks to](https://codegolf.stackexchange.com/questions/213543/sequences-of-distinct-positive-integers/213546?noredirect=1#comment500174_213546) [Sisyphus](https://codegolf.stackexchange.com/users/48931/sisyphus)
-1 more byte [thanks to](https://codegolf.stackexchange.com/questions/213543/sequences-of-distinct-positive-integers?answertab=votes#comment500194_213546) Sisyphus
## How it works
```
œ!RẎṢiƇ - Main link. Takes n on the left
  R     - Yield [1, 2, ..., n]
œ!      - For each i = 1, 2, ..., n, yield all length-n permutations of [1, 2, ..., n]
   Ẏ    - Join into a single list
    Ṣ   - Sort
      Ƈ - Keep those where
     i  -   The 1-based index of n is non-zero (i.e n is in the list)
```
[Answer]
# [K (ngn/k)](https://bitbucket.org/ngn/k), 24 bytes
```
{t@<t:(x=|/)#??'1++!x#x}
```
[Try it online!](https://tio.run/##y9bNS8/7/z/NqrrEwabESqPCtkZfU9neXt1QW1uxQrmi9n@agvF/AA "K (ngn/k) – Try It Online")
[Answer]
# [Scala](http://www.scala-lang.org/), ~~132~~ ~~124~~ 117 bytes
```
n=>1.to(n-1).toSet.subsets().flatMap(_.+(n).toSeq.permutations).toSeq.sorted(Ordering.Implicits.seqOrdering[Seq,Int])
```
* Thanks to [user](https://codegolf.stackexchange.com/users/95792/user) for -7 characters!
[Try it online!](https://scastie.scala-lang.org/O5hgqCR8R2iDufhaSD7oDA)
[Answer]
# JavaScript (ES6), ~~89~~ 82 bytes
This started as a port of [@xnor's method](https://codegolf.stackexchange.com/a/213547/58563) and then was golfed the JS way from there.
```
f=(n,s=[],i)=>i>n?[]:[...!i^s.includes(i||n)?[]:i?f(n,[...s,i]):[s],...f(n,s,-~i)]
```
[Try it online!](https://tio.run/##VYxNDoIwEIX3nmJMXLSxNrpwA6IHITUYLDiGTJURN4BXxymuXL28v@9@eV@4bPHx2lC4@mmqMkWGs9wZ1NkRj3TKXZJba5d4ZotUNt3Vs8JhIB0rPFVyiAM26HSSszNiYshm80Htpiq0iiCDXQoEB9htRddrDf0CoPUsjax1Kq4MxKHxtgm1KuJl1dMIiYjsbOOpft1GYP/sPJVesS7mG8pfwPsf8h8T0fPoP56jcTFOXw "JavaScript (Node.js) – Try It Online")
### Commented
```
f = (                      // f is a recursive function taking:
  n,                       //   n   = input
  s = [],                  //   s[] = current sequence
  i                        //   i   = counter, initially undefined
) =>                       //
  i > n ?                  // if i is greater than n:
    []                     //   stop the recursion and return an empty array
  :                        // else:
    [                      //   build a new array:
      ...                  //     append the following values:
      !i ^                 //       if i = 0 and s[] does not include n
      s.includes(i || n) ? //       OR i > 0 and s[] includes i:
        []                 //         append nothing
      :                    //       else:
        i ?                //         if i > 0:
          f(n, [...s, i])  //           append all the values returned by a
                           //           recursive call with i appended to s[]
        :                  //         else:
          [s],             //           append s[]
      ...                  //     append all the values returned
      f(n, s, -~i)         //     by a recursive call with i + 1
    ]                      //   end of new array
```
[Answer]
# [SageMath](https://www.sagemath.org/), 93 bytes
```
lambda n:sorted(sum([[*Permutations(l)]for l in Subsets(range(1,n+1))if n in l],[]),key=list)
```
[Try it online!](https://sagecell.sagemath.org/?z=eJw1i7EKwjAURfd-xaVQeE_j0MWhUL9BcKwdUpJIMH2VvHTQr9cWPNvl3BP6e5XsPDkL6XTJxTvSdaZhOFx9ntdiS1xEKfEYloyEKLitk_qilK08PLVGji1zDJBNptEMI5unf_cpauGq2rpd_f84c1fhh6JHIOF9vHKUQnXjcLqANH48Gsc1GpCY5IWU2UD5CyZUNSk=&lang=sage&interacts=eJyLjgUAARUAuQ==)
Inputs \$n\$ and returns a list of all permutations of every \$s\$ in \$\{s\subseteq\{1,2,\dots,n\} \mid n\in s\}\$ sorted lexicographically.
### Explanation
```
lambda n:                           # function taking integer n  
                                    # returning a list of  
  [*Permutations(l)]for l in        # all permutations  
     Subsets(range(1,n+1))          # of all subsets of {1,2,...,n}  
       if n in l                    # that have n as an element  
         sum( . . . ,[])            # flattened  
           sorted( . . . ,key=list) # and sorted lexicographically     
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~55~~ 45 bytes
```
Do[i!=##2&&##~#0~i,{i,0!=##||Print@{##2};#}]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b73yU/OlPRVlnZSE1NWblO2aAuU6c6U8cAJFRTE1CUmVfiUA2UrbVWro1V@5/m4Jqcke@grFYXnJyYVxeUmJee6mD6HwA "Wolfram Language (Mathematica) – Try It Online")
Inspired by xnor's python solution, and borrows from my answers to some [prior](https://codegolf.stackexchange.com/a/185137/81203) [problems](https://codegolf.stackexchange.com/a/191556/81203).
Prints the list of sequences.
Recursively traverses through all permutations of subsequences of `1..n` in lexicographic order, printing those which contain `n`.
```
0!=##||             (* If n is in the current sequence, *)
  Print@{##2};      (*   output. *)
{i, % ;#}           (* for i=1..n: *)
Do[i!=##2&&         (*   if i is not in the current sequence, *)
    ##~#0~i, % ]&   (*     append it and recurse. *)
```
[Answer]
# Scala, 87 bytes
```
n=>1.to(n-1).toSet.subsets.toSeq.flatMap(_.toSeq:+n permutations)sortBy(_ mkString " ")
```
[Try it online!](https://scastie.scala-lang.org/ilXuJlPYQxyGExZuIgi8aQ)
[Answer]
# Scala 3, 130 bytes
```
| =>(for< <-1 to|;> <-1 to|combinations<if>toSet|;? <- >permutations yield?)sortBy(_.map("%10s"format _ replace(' ','0'))mkString)
```
[Try it online!](https://scastie.scala-lang.org/MgYAPttOQCCwgmqkLX04mg)
Readable variable names are so overrated. Who needs `n` when you can have `|`?
# Scala, ~~140~~ 137 bytes
```
| =>(for{< <-1 to|
> <-1 to|combinations<if>toSet|
? <- >permutations}yield?)sortBy(_.map("%10s"format _ replace(' ','0')).mkString)
```
Wow, this got long.
[Try it online](https://scastie.scala-lang.org/XTxVkIU6Q029PmWndFDUNw)
Ungolfed, with comments and sensible variable names:
```
n => 
 (for {
    i <- 1 to n                //For every i in the range [1..n]
    c <- 1 to n combinations i //Every subset of [1..n] of size i
    if c contains n            //Make sure the max is n first
    p <- c.permutations        //For every permutation of that subset
  } yield p                    //Yield that permutation
 ) sortBy( //Sort it with this function
     _.map(                    //For every number in the sublist
       "%10s"format _ replace(' ','0') //Pad it on the right to a width of ten using 0
      ).mkString //Smoosh it into one string
   )
```
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 46 bytes
```
Ｎθ≔⟦υ⟧ηＦθ«≔ηζ≔⟦υ⟧ηＦ⊕ιＦζ⊞η⁺⟦κ⟧Ｅλ⁺μ¬‹μκ»ＩΦ⊕η⁼θ⌈ι
```
[Try it online!](https://tio.run/##XU69CsIwEJ6bp8h4gTg5dhJRKGjpXhxijSY0Sdv8iFR89piUDuJNd9/vdYLZbmAqxsqMwddBX7mFiZRo55x8GGjDhWKR7vtgcSLwGxUrJSieE1H8K4tFWpnOcs2N5zeQhOAFnAlughPZ2qjgoO2T58xGUCugKa4HDyfulr0neUr0QY2VxsOeOQ9HqXx68rdAEIoPU2DKwZQDX1IHnWuzO8Zt3DzVFw "Charcoal – Try It Online") Link is to verbose version of code. Directly generates all sequences containing values up to `n` in lexicographical order and then prints those containing `n`. Outputs values on separate lines with sequences double-spaced. Explanation:
```
Ｎθ
```
Input `n`.
```
≔⟦υ⟧η
```
Start off with a list containing an empty sequence.
```
Ｆθ«
```
Loop `n` times.
```
≔ηζ
```
Save the previous list of sequences.
```
≔⟦υ⟧η
```
Start a new list containing an empty sequence.
```
Ｆ⊕ι
```
Loop from `0` to `i` inclusive.
```
Ｆζ
```
Loop over the previous list of sequences.
```
⊞η⁺⟦κ⟧Ｅλ⁺μ¬‹μκ
```
Make a space in the sequence for the inner index and add that at the beginning of the sequence. For example, if current sequence was `1 0`, then an inner index of `0` would give `0 2 1`, an inner index of `1` would give `1 2 0` and an inner index of `2` would give `2 1 0`. This is required so that the sequences are generated in lexicographical order. (Charcoal doesn't have an easy way to sort.)
```
»ＩΦ⊕η⁼θ⌈ι
```
Increment the sequences and print those containing `n`.
[Answer]
# [Wolfram Language](https://www.wolfram.com/language/), 109 bytes
```
{a_,b___}~p~{c_,d___}:=If[a==c,{b}~p~{d},a~Order~c]
Sort[Join@@Permutations/@Append@#/@Subsets@Range[#-1],p]&
```
[Try it online!](https://tio.run/##Hcy7CsMgFIDhva8R6GQJpVtBOB3bpSEZReR4ax2iomaS@Or2sv3wwb9ieZsVi1PYe0VBpBBib7FVJYj@9ZXeLUNKFanyD3on2J5Jm9QUP1i6hFTYIzgPMJm0buV7Cz6PcIvReA3DCMsmsykZZvQvw4bTmZPIj31Kzhdm4cL7Bw "Wolfram Language (Mathematica) – Try It Online")
Thanks to [@att](https://codegolf.stackexchange.com/users/81203/att) for a suggestion that saves four bytes.
The first line of this answer is actually a lexicographic ordering function since the default sorting is not lexicographic. It checks if the first two terms of two lists are equal: if so it recurses on the remainder of the lists, and if not it returns the ordering of the two first elements. I expected to need to provide special cases for when one arrives at empty lists, but it appears that in the case of not returning a proper value, `Sort` falls back to the default `Order` function, which works fine.
The function itself generates all subsets of `{1,2,...,n-1}`, appends `n` to each, then generates the permutations of each. These are then sorted into lexicographic ordering using the function defined.
**att's impressive 74-byte answer:** (it feels improper to take credit for it, but I think it deserves recognition)
```
SortBy[Join@@Permutations/@Append@#/@Subsets@Range[#-1],aa~PadRight~#]&
```
`` is [\[Function]](http://reference.wolfram.com/language/ref/character/Function.html).
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 10 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Lœ€æ€`êʒIå
```
[Try it online.](https://tio.run/##yy9OTMpM/f/f5@jkR01rDi8DEgmHV52a5Hl46f//xgA)
**Explanation:**
```
L           # Push a list in the range [1,(implicit) input]
 œ          # Get all permutations of this list
  €         # Map each permutation to:
   æ        #  Get its powerset
    €`      # Flatten it one level down
      ê     # Sort and uniquify this list of lists
       ʒ    # Filter it by:
        Iå  #  Check if the current list contains the input
            # (after which the result is output implicitly)
```
[Answer]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), 36 bytes
```
{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/v/pRx/JHHauqH/Vu1X/Uu6L8UUfXoRVATu2jrmYdfSBxaIXGo65FOjqHVmjqA2XaJj/qaSrITSwBCpY/apsAUvo/DczoA6p@1LvmUe@WQ@uNH7VNfNQ3NTjIGUiGeHgG/09TMAYA "APL (Dyalog Extended) – Try It Online")
Uses [Bubbler's APL tip](https://codegolf.stackexchange.com/a/211449/80214) for generating subsequences of a vector.
## Explanation
```
{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}
                                w←⍵  assign input to w for later
                          ⌂pmat⊢     generate matrix of all permutations of 1..input
                                     (⌂ is an extended symbol)
                         ↓           convert matrix to list of vectors
                 (⊢,,¨)/¨            generate all subsequences of each,
                                     which include the last item
            ⊃,/⊃¨                    remove nesting for each, and join into a list of vectors
    ⍵/⍨                              filter the vectors by:
       w∊¨⍵                          whether the input exists in them
  ∪                                  remove duplicates
 ∧                                   Sort lexicographically (Extended symbol)
```
[Answer]
# [Perl 5](https://www.perl.org/), 52 bytes
```
$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n
```
[Try it online!](https://tio.run/##K0gtyjH9/18lz1Yl3jo3sUBfQ09TTyvGsCY6zlBXJS9Wv0ZRXyVPv6amOLFSpzi/qETBUE9PJU@hQiXv/3@Tf/kFJZn5ecX/dX3LTPUMDf7r5uUAAA "Perl 5 – Try It Online")
Can run like this for n=3:
```
echo 3 | perl -nlE'$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n'
```
But doesn't work for n > 9. For n=7 it used twelve seconds on my humble laptop and then about ten minutes for n=8.
[Answer]
# [Gaia](https://github.com/splcurran/Gaia), 9 bytes
```
┅zf¦e¦Ė⁇ȯ
```
[Try it online!](https://tio.run/##ARoA5f9nYWlh///ilIV6ZsKmZcKmxJbigYfIr///Mw "Gaia – Try It Online")
Generate all permutations of subsets of `[1..n]`, filter out those not containing `n`, and sort.
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-h`](https://codegolf.meta.stackexchange.com/a/14339/), ~~12~~ 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
õ à cá ÍüøU
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LWg&code=9SDgIGPhIM38%2bFU&input=MwotUg)
```
õ à cá ÍüøU     :Implicit input of integer U
õ               :Range [1,U]
  à             :Combinations
    c           :Flat map
     á          :  Permutations
       Í        :Sort
        ü       :Group and sort by
         øU     :  Contains U?
```
[Answer]
# [Perl 5](https://www.perl.org/) `-MList::Util=uniq -na`, 106 bytes
It's twice as long as the other Perl 5 answer, but it works (slowly) for any `n`;
```
map/\b@F\b/&&!/\b(\d+),.*\b\1\b/&&say,uniq sort map{s/,+/,/g;s/^,+|,+$//gr}glob join',',("{",1..$_,"}")x$_
```
[Try it online!](https://tio.run/##HYy9CsIwGABfpYbSH/M1n0G6VAQnJx3dgqVBKZGY1CaKUvvqxup2HMd1516XIVybDoXcbIXEJJlNmIkTzYHNhRT8L13zgrtRt8jZ3kdTPzgEioDtyuER6BtojNj2Y6utjC5WmRRSyMhAgDMW10BGkj/jOoTlx3ZeWeNCsd8p56vq4JVe/@aTeZSML0JhdPMF "Perl 5 – Try It Online")
]