Sequences of distinct positive integers

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)\$ sequences.)

---

This is a code-golf challenge, so the shortest code wins.

Answer 1

Python 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!

Python 3 lets us save some bytes with set unpacking.

Python 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!

Answer 2

Husk, 9 bytes

Of€¹umu´π

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 3

Brachylog, 10 bytes

{⟦₆⊇,?p}ᶠo

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 4

Haskell, 60 bytes

n!b=[[]|all(<n)b]++[k:c|k<-b,c<-n!filter(/=k)b]
f n=n![1..n]

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 5

Jelly, 10 9 8 7 bytes

œ!RẎṢiƇ

Try it online!

-1 byte thanks to Sisyphus

-1 more byte thanks to 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 6

K (ngn/k), 24 bytes

{t@<t:(x=|/)#??'1++!x#x}

Try it online!

Answer 7

Scala, 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 for -7 characters!

Try it online!

Answer 8

JavaScript (ES6),  89  82 bytes

This started as a port of @xnor's method 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!

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 9

SageMath, 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!

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 10

Wolfram Language (Mathematica), 55 45 bytes

Do[i!=##2&&##~#0~i,{i,0!=##||Print@{##2};#}]&

Try it online!

Inspired by xnor's python solution, and borrows from my answers to some prior problems.

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 11

Scala, 87 bytes

n=>1.to(n-1).toSet.subsets.toSeq.flatMap(_.toSeq:+n permutations)sortBy(_ mkString " ")

Try it online!

Answer 12

Scala 3, 130 bytes

| =>(for< <-1 to|;> <-1 to|combinations<if>toSet|;? <- >permutations yield?)sortBy(_.map("%10s"format _ replace(' ','0'))mkString)

Try it online!

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

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 13

Charcoal, 46 bytes

Ｎθ≔⟦υ⟧ηＦθ«≔ηζ≔⟦υ⟧ηＦ⊕ιＦζ⊞η⁺⟦κ⟧Ｅλ⁺쬋μκ»ＩΦ⊕η⁼θ⌈ι

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 14

Wolfram 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!

Thanks to @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].

Answer 15

05AB1E, 10 bytes

Lœ€æ€`êʒIå

Try it online.

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 16

APL (Dyalog Extended), 36 bytes

{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}

Try it online!

Uses Bubbler's APL tip 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 17

Perl 5, 52 bytes

$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n

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 18

Gaia, 9 bytes

┅zf¦e¦Ė⁇ȯ

Try it online!

Generate all permutations of subsets of [1..n], filter out those not containing n, and sort.

Answer 19

Japt -h, 12 11 bytes

õ à cá ÍüøU

Try it

õ à cá ÍüøU     :Implicit input of integer U
õ               :Range [1,U]
  à             :Combinations
    c           :Flat map
     á          :  Permutations
       Í        :Sort
        ü       :Group and sort by
         øU     :  Contains U?

Answer 20

Perl 5 -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!