Iterative Smallest Complement

Question

For this challenge, we will define the "complement" of a list of integers A as being any list B such that the union of A and B is a list of consecutive integers with no repeats.

In other words, B is the complement of A if

• B has all of the integers between the minimum and maximum of A which are missing from A, and
• B has none of the integers present in A

For example: [2, 4, 6, 7] is a complement of [1, 3, 5, 8, 9], [1, 3, 5], and [3, 5], but it is not a complement of [1, 2, 3, 5] or [1, 3, 5, 9].

Worth noting: For a list of consecutive integers, a complement may be the empty list, as no integers are "missing" between the minimum and maximum.

Any given list of integers with no repeats has infinitely many complements (proof left as an exercise for the reader), but has exactly one smallest complement, which itself has this very same property.

For example, if we start with the list [1, 2, 3, 5, 8, 13] and repeatedly find the smallest complement, we get this chain of lists:

[1, 2, 3, 5, 8, 13]
[4, 6, 7, 9, 10, 11, 12]
[5, 8]
[6, 7]
[]

The smallest complement of the empty list is the empty list, so we can stop here.

Challenge

Given a list of non-repeating positive integers A, output the A's smallest complement, followed by that list's smallest complement, all the way until the empty list.

Rules

• You may choose to include or omit the input list in your output.
• You may choose to include or omit the empty list in your output.
• The input list will always have complements. (i.e. the list will never contain duplicates)
• The input will be sorted.
• The input will never be the empty list.
• The input will never contain 0 or negative integers. (although they are well defined)
• This is code-golf, so shortest code in bytes wins.

Examples

Outputs will include both the original list and the empty list, for clarity

input => output
[1, 3, 5, 7, 9] => [[1, 3, 5, 7, 9], [2, 4, 6, 8], [3, 5, 7], [4, 6], [5], []]
[5, 10, 15, 20] => [[5, 10, 15, 20], [6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19], [10, 15], [11, 12, 13, 14], []]
[5, 10, 15] => [[5, 10, 15], [6, 7, 8, 9, 11, 12, 13, 14], [10], []]
[1, 2, 6, 7, 11, 12] => [[1, 2, 6, 7, 11, 12], [3, 4, 5, 8, 9, 10], [6, 7], []]
[1, 2, 3] => [[1, 2, 3], []]
[5, 6, 7] => [[5, 6, 7],  []]

Answer 1

R, 45 44 bytes

f=function(r)r&f(print(setdiff(r:max(r),r)))

Attempt This Online!

Derived without peeking at pajonk's R answer, but ended-up with a pretty similar approach ...

Answer 2

Husk, 5 bytes

U¡S-…

Try it online!

 ¡     # Apply function repeatedly, collect values in infinite list:
   -   # list difference of
  S    # last result (or input for first iteration)
  S …  # and last result with gaps filled with numeric ranges;
U      # Finally, get longest prefix of the list with all unique elements.

Answer 3

K (ngn/k), 18 bytes

Includes input and empty list (!0) in the output.

{(x,/x_!0^*|x)^x}\

Try it online!

{ ... }\ Converges; Call the lambda repeatedly until the value doesn't change.
( ... )^x The range computed in the parentheses without the elements in x.

*|x Last (largest) value in x. This returns 0N if x is empty, then 0^ replaces 0N with 0.
! range from 0 to this value value (exclusive).
x_ cut this range at the indices given by x. Because the first slice is omitted, this gets rid of the numbers up to the minimum of x.
x,/ Flatten the cutted list, prepending x. We need to prepend x to get the shape right for the empty list.

Instead of converges we could use whiles to avoid dealing with the empty list. This would save 3 bytes in the lambda, but add 4 on the outside:

(::){(,/x_!*|x)^x}\

Try it online!

Answer 4

R, 55 50 bytes

Edit: -5 bytes thanks to @Giuseppe.

f=function(v)if(s<-setdiff(v:max(v),print(v)))f(s)

Try it online!

Prints the inital list but not the empty one. Terminates with an error.

In R==4.1 replace function with \ to achieve 43 bytes (still longer than @Dominic van Essen's answer working in R>=4.1 after also implementing this notation there). This doesn't work in R>=4.2.0 (and consequently in ATO), due to introduction of a strict check for argument length for if.

Explanation outline

1. Compute sequence from min to max with v:max(v) (: takes first element of a vector and as input is sorted, this is the minimum).
2. Take set difference setdiff of this and input (we print it here and print conveniently returns its argument).
3. Assign this to s.
4. if takes the first element of a vector and checks if it's truthy (not 0 or FALSE) and errors for empty input. Essentially, check if s is nonempty.
5. Recurse.

Answer 5

Python 3, 56 bytes

f=lambda l:l and[l]+f(sorted({*range(l[0],l[-1])}-{*l}))

Try it online!

Answer 6

Vyxal, 7 bytes

≬₌gGṡ⊍İ

Try it Online! or Try all the tests

Input list not included, empty list is.

Explained

≬₌gGṡ⊍İ
≬-----     # Next three elements as a function:
 ₌gG       #   Get the smallest and largest item of the argument
    ṡ      #   Create an incluse range between those values
     ⊍     #   and set xor with the original argument
      İ    # Repeat that function until the result is no longer unique, collecting results

Answer 7

J, 18 bytes

(-.~{:-.&i.{.)^:a:

Try it online!

thejonymyster has allowed this output... since J only supports heterogeneous lists with boxing, and since 0 is disallowed in the input, I am displaying the output as a homogeneous matrix with 0 fill, so that the successive lists are simply each row, without the 0 fill:

1 2 3 5  8 13  0
4 6 7 9 10 11 12
5 8 0 0  0  0  0
6 7 0 0  0  0  0
0 0 0 0  0  0  0

Note that, if desired, we could add boxing for 3 more bytes.

• (...)^:a: Until a fixed point is reached, collecting results, do the following...
• -.~{:-.&i.{. Remove -. the input from 0 1 ... <largest element - 1> without 0 1 ...<smallest element - 1>

Answer 8

Pyth, 9 8 bytes

#p=-rhQe

Try it online!

#p=(Q)-rhQe(QQ)
              // Implicitly initialize Q as the input
#             // Repeat until an error occurs:
     rhQeQ    // Range from first to last element of Q...
    -     Q   // ...with elements of Q removed
  =Q          // Set Q to the result
 p            // Print  

Answer 9

Zsh, 44 bytes

<<<$@
a=({$1..$@[$#]})
(($#))&&$0 ${a:|argv}

Try it online!

<<<$@             # output arguments
a=({$1..$@[$#]})  # all integers between first and last args
(($#)) &&         # if there was at least one argument
    $0 ${a:|argv}  # recurse with set difference between $a and the arguments

Using $argv is needed in the ${a:|b} notation, ${a:|@} does not work.

Answer 10

JavaScript (ES10), 66 bytes

The empty list is included. The input list is not.

f=a=>a+a&&[b=a.flatMap(p=g=v=>++p-v?[p,...g(v)]:(p=v,[])),...f(b)]

Try it online!

Or as ES6 (also 66 bytes):

f=a=>a+a&&[a.map(p=g=v=>++p-v?g(v,b.push(p)):p=v,b=[])&&b,...f(b)]

Try it online!

Answer 11

BQN, 23 bytes

{𝕊¬∘∊⟜𝕩⊸/𝕩⊑⊸↓↕⌈´•Show𝕩}

Try it here!

Terminates with error.

Explanation

Input is x.

• •Show𝕩 output x
• ↕⌈´ exclusive range from 0 to max of x
• 𝕩⊑⊸↓ drop (first element in x) elements
• ¬∘∊⟜𝕩⊸/ filter elements not in x
• 𝕊 recurse

Answer 12

Factor + math.unicode, 51 50 bytes

[ [ 3 dupn . minmax [a,b] swap ∖ ] until-empty ]

Input list is included; empty list is omitted.

Try it online!

• [ ... ] until-empty Call [ ... ] on the input repeatedly until it is empty.

         ! { 1 3 5 7 9 }
3        ! { 1 3 5 7 9 } 3
dupn     ! { 1 3 5 7 9 } { 1 3 5 7 9 } { 1 3 5 7 9 }
.        ! { 1 3 5 7 9 } { 1 3 5 7 9 }   ((output to stdout))
minmax   ! { 1 3 5 7 9 } 1 9
[a,b]    ! { 1 3 5 7 9 } { 1 2 3 4 5 6 7 8 9 }
swap     ! { 1 2 3 4 5 6 7 8 9 } { 1 3 5 7 9 }
∖        ! { 2 4 6 8 }    ((set difference))
         !   ((and so forth...))

Answer 13

Haskell, 65 49 bytes

-10 bytes thanks to @Lynn

g[]=[];g x=x:g[e|e<-[head x..last x],notElem e x]

Answer 14

Charcoal, 15 bytes

Ｗθ«≔⁻…⌊θ⌈θθθ⟦Ｉθ

Try it online! Link is to verbose version of code. Does not output the initial list. Would output the final list except that Charcoal has no output for an empty list. Explanation:

Ｗθ«

Repeat until the list is empty.

≔⁻…⌊θ⌈θθθ

Subtract the list from the range of its lowest to highest elements.

⟦Ｉθ

Output the new list with separation from the previous list.

Answer 15

Burlesque, 39 bytes

1{sa1.>{Jl_g_/vjr@j\\}q{}IE}C~J{}Fi+..+

Try it online!

The only bit which is required to compute this is

1{Jl_g_/vjr@j\\}C~

Unfortunately, this crashes on reaching a 0/1 element block because it tries to pull head/tail from an empty list.

1        # Number of elements Continue forever keeps from the top of the stack
{
 sa1.>   # Length of block at least 2 elements
 {
  J      # Duplicate
  l_g_/v # Get head and tail of list
  jr@    # Range head..tail 
  j\\    # List difference with original
 }
 q{}IE   # If list too short return empty list
}C~      # Continue forever
J{}Fi    # Find the first occurrence of empty list 
+..+     # Take that many (including an empty element)

Answer 16

05AB1E, 8 bytes

Δ=WsàŸyK

Outputs the intermediate lists separately to STDOUT; includes both the input-list and empty-list. Stops with an error.

Try it online or verify all test cases.

Explanation:

Δ         # Loop until the result no longer changes
          # (although it'll basically loop until the error in this case)
 =        #  Print the current list with trailing newline (without popping)
          #  (which will use the implicit input-list in the first iteration)
  W       #  Push its minimum (without popping)
   s      #  Swap so the list is at the top again
    à     #  Pop and push its maximum
     Ÿ    #  Pop both, and push a list in the range [min,max]
          #  (the min/max of an empty list are ""; so here it'll error)
      y   #  Push the current list again
       K  #  Remove all those values from the [min,max]-ranged list

Answer 17

Ruby, 34 bytes

f=->a{a[0]&&f[p [*a[0]..a[-1]]-a]}

Try it online!

Answer 18

Retina 0.8.2, 80 bytes

$
;¶$%`
\d+
$*
%(M!&`^.+;|(1+)$(?<!^\1.*)(?<!\b\1\b.*)
O`
)`¶
,
1+
$.&
}`;¶$

;

Try it online! Explanation:

$
;¶$%`

Duplicate the last line and mark the previous line as not to be altered.

\d+
$*

Convert to unary.

%(`
)`

Run the next three commands separately for each line, so that they don't accidentally clobber one another.

M!&`^.+;|

Just output the previous lines in full, so nothing happens...

(1+)$

... but for the last line, output overlapping substrings of the final run of 1s...

(?<!^\1.*)

... that are greater than the first run of 1s...

(?<!\b\1\b.*)

... and do not match any of the runs of 1s.

O`

Sort the lines into ascending order.

¶
,

Join them with commas.

1+
$.&

Convert to decimal.

;¶$

If the were no matching runs of 1s, then just undo everything, so that the loop stops repeating.

}`

Repeat the above commands until the buffer stops changing.

;

Remove the markers on the previous lines.

Answer 19

Rust, 138 bytes

let f=|l:Vec<u8>|std::iter::successors(Some(l),|l|if l.len()>0{Some((l[0]..l[l.len()-1]).filter(|i|!l.contains(i)).collect())}else{None});

Returns a generator.

Goal was to get the longest answer possible, right?

try it yourself

Answer 20

GeoGebra, 93 bytes

l={
InputBox(l
a=IterationList(Remove(Min(L)...Max(L),L),L,{l},Length(l
Take(a,1,IndexOf({},a

Input as comma separated numbers in the input box. Output is the list l1.

Try It On GeoGebra!

Try It On GeoGebra! (with example test case)

Answer 21

Wolfram Language (Mathematica), 55 bytes

NestWhileList[Complement[Range@@MinMax@#,#]&,#,#!={}&]&

Try it online!

Answer 22

Python 3, 50 bytes

f=lambda K:[*K]and[K]+f({*range(min(K),max(K))}-K)

Try it online!

Takes input as a set rather than a list so I can use the more efficient set difference operator. Output will not be sorted. Basic logic to build a list efficiently copied from @m90