Form a subset that is a continuous range

Given a list of lists of positive integers, output a subset of them so their union forms a continuous non-empty range with no numbers missing. For example, consider this input:

[
[1, 2, 3, 5],
[2, 4, 6],
[7, 9, 11]
]


The union of the first 2 forms a continuous sequence: [1, 2, 3, 4, 5, 6] with no numbers missing. Adding the last one would create [1, 2, 3, 4, 5, 6, 7, 9, 11] which is missing 8 and 10 so would not be a valid answer.

Output can be either the indexes of the included lists or the lists themselves.

Lists are guaranteed to be sorted, and the list of lists will also be sorted lexicography. All lists will have at least one element. There may be more than one valid solution, if so you may choose output any of them, or all of them, or some of them. If you output multiple solutions all must be valid and they must be clearly separated.

There will never be no solutions.

Test cases

Input Output
[[1, 2, 3]] 0
[[1, 3], [2, 4]] 0, 1
[[2, 4], [4, 23], [8, 10], [8, 12], [9, 13], [10, 23], [11, 14]] 2, 3, 4, 6
[[1, 3], [2, 4], [5,7], [6,8]] 0,1 OR 2,3 OR 0,1,2,3
[[1, 17], [2,23], [3,42], [4,17], [5, 3912], [6]] 5
• Would a list that include more numbers to include in the final list have precendent over a list that include fewer? For example: [[1,5][5,6][5,6,7]], could just be 2?
– JvdV
Commented Jan 10, 2023 at 18:16
• @JvdV if there are multiple possible solutions you may choose to output any of them. No specific preference. Commented Jan 10, 2023 at 18:17
• Can we output the empty list as a solution? Commented Jan 12, 2023 at 10:30
• No, as the problem states "a continuous non-empty range" Commented Jan 12, 2023 at 10:31

Factor + math.combinatorics math.unicode, 61 57 bytes

[ all-subsets rest [ concat dup minmax [a,b] ⊃ ] find ]


Try it online!

Returns the lists that make up the range. Returns the first solution it finds.

• all-subsets rest Powerset sans the empty set.
• [ ... ] find Find the first element that returns true when [ ... ] is run on it.
• concat The union of all sets in a sequence (with duplicates, but it doesn't matter).
• dup minmax [a,b] Create a range from the minimum and maximum elements in the union.
• ⊃ Is the union a superset of the range?

Pyth, 12 bytes

f!-.+{SsT1ty


Try it online!

Returns a list of all answers, each in list of lists form.

Explanation

f!-.+{SsT1tyQ    # implicitly add Q
# implicitly assign Q = eval(input())
yQ    # power set of Q
t      # all but the first element (thus excluding the empty element)
f                # filter on lambda T
sT        #   flatten T
S          #   sort
{           #   deduplicate
.+            #   take the deltas (should be all 1s if we have a continuous range)
-      1       #   remove all instances of 1
!               #   not (will only be true for the empty list)


Jelly, 9 bytes

ŒPṬSṠṢƑƲƇ


A monadic Link that accepts a list of lists of positive integers and yields a list of the valid lists of lists for which the union forms a continuous range.

Try it online! Or see the test-suite.

How?

ŒPṬSṠṢƑƲƇ - Link: list of lists of positive integers, A
ŒP        - powerset (of A)
Ƈ - keep those for which:
Ṭ       -     untruth - e.g. [[2], [2, 5, 7]] -> [[0, 1], [0, 1, 0, 0, 1, 0, 1]]
S      -     sum (columns of that)           -> [0, 2, 0, 0, 1, 0, 1]
Ṡ     -     sign                            -> [0, 1, 0, 0, 1, 0, 1]
Ƒ   -     is invariant under?:
Ṣ    -       sort                          -> 0


If we may also identify the empty set (as producing a continuous range of zero positive integers) then $$\8\$$ bytes: ŒPFṬṢƑƊƇ - test suite.

Vyxal221817 15 or 10 bytes

This code output resulting range:

ṗƛÞfUs;'¯U1w⁼;,


Try it online!

and this (@lyxal) - the lists that are used in the range:

ṗꜝ'ƒ∪s¯1=A


Try it online!

• Here's a 10 byte answer that also works. It's similar to yours, but just uses a few tricks like the reduce-by modifier and keep only truthy. Commented Jan 11, 2023 at 3:34
• @lyxal Hmmm but output looks not exactly what is required! For [[2, 4], [4, 23], [8, 10], [8, 12], [9, 13], [10, 23], [11, 14]] my: ⟨ ⟨ 8 | 9 | 10 | 11 | 12 | 13 | 14 ⟩ ⟩ and yours ⟨ ⟨ ⟨ 8 | 10 ⟩ | ⟨ 8 | 12 ⟩ | ⟨ 9 | 13 ⟩ | ⟨ 11 | 14 ⟩ ⟩ ⟩ Or I miss smth? Commented Jan 11, 2023 at 4:58
• answers need to output the lists that are used in the range Commented Jan 11, 2023 at 5:08

Japt, 15 bytes

Outputs all possible solutions as the original arrays.

à fÊkÈrâ Íän dÉ


Try it

Python, 150 bytes

lambda l:[x for i in range(len(l))for x in combinations(l,i+1)if(s:=sorted({*chain.from_iterable(x)}))==[*range(s[0],s[-1]+1)]]
from itertools import*


Attempt This Online!

05AB1E, 7 or 10 bytes

ā<æ¦ʒè˜ê¥P


Outputs all possible result, by outputting the 0-based indices like the challenge description.

æ¦ʒ˜ê¥P


Outputs all possible results, by outputting the lists of lists themselves.

If we're also allowed to include an empty list, the ¦ can be dropped in both programs for -1 byte.

Explanation:

ā           # Push a list in the range [1, (implicit) input-length]
<          # Decrease each by 1 to the range [0, length)
æ         # Get the powerset of this
¦        # Remove the empty leading list
ʒ       # Filter the list of lists by:
è      #  Index each into the (implicit) input list of lists
˜     #  Flatten it
ê    #  Sorted-uniquify it
¥   #  Get all deltas / forward-differences
P  #  Take the product (only 1 is truthy in 05AB1E)
# (after which the filtered result is output implicitly)


The second program is similar, but without ā< so the powerset is done directly on the input-list of lists, and therefore also without è.

JavaScript (Node.js), 84 bytes

f=([x,...y],v=[])=>x?f(y,[...v,x])||f(y,v):v.flat().map(i=>y[i]=0)|/0,,/.test(y)?0:v


Try it online!

f=([x,...y],v=[])=>
x?
f(y,[...v,x])||f(y,v)   // [] is always a continuous range, so it's last tested
:
v.flat().map(i=>y[i]=0) // Writing 0, so if v.flat().length==1 then it returns 0, not bother bitOR
|/0,,/.test(y)?0:v      // Is there hole between, ,,,0,0,0,0 is fine, ,,,0,0,,0 isn't


JavaScript (ES6), 81 bytes

-1 thanks to @l4m2

Returns a single solution as a space-separated string of integer lists.

f=([v,...a],m,o)=>v?f(a,m,o)||f(a,v.map(k=>m|=1<<k)|m,[o]+v+' '):(m|=m-1)&m+1?0:o


Try it online!

• 81
– l4m2
Commented Jan 10, 2023 at 17:54

Charcoal, 30 bytes

ＩΦＥＸ²ＬθΦθ﹪÷ιＸ²μ²∧ι¬⁻…·⌊Σι⌈ΣιΣι


Attempt This Online! Link is to verbose version of code. Outputs all solutions. Explanation:

    ²                           Literal integer 2
Ｘ                            Raised to power
θ                         Input list
Ｌ                          Length
Ｅ                             Map over implicit range
θ                       Input list
Φ                        Filtered where
ι                    Outer value
÷                     Integer divided by
²                  Literal integer 2
Ｘ                   Raised to power
μ                 Inner index
﹪     ²                Is odd
Φ                              Filtered where
ι              Current result
∧               Logical And
ι       Current result
Σ        Flattened
⌊         Minimum
ι    Current result
Σ     Flattened
⌈      Maximum
…·          Inclusive range
⁻            Remove elements present in
ι  Current result
Σ   Flattened
¬             Logical Not i.e. is empty
Ｉ                               Cast to string
Implicitly print


The output format is as follows: Each result is triple-spaced from each other, while within a result, the sets that comprise the result are double-spaced from each other and each element is output on its own line.

import Data.List


Try it online!

Brachylog, 9 bytes

⊇.cod~⟦₂∧


Try it online!

Generates solution with the largest number of sublists first.

Explanation

⊇.           Output is a sublist of the input
cod        Concatenate, sort, remove duplicates
~⟦₂     The resulting list must be a range between 2 integers
∧


BQN, 35 bytes

({(⌈´¬⌊´)=≠}¨/⊢)∘((⍷∾)¨(⥊(↕2˘)/¨<))


Try it online!

Explanation

({(⌈´¬⌊´)=≠}¨/⊢)∘((⍷∾)¨(⥊(↕2˘)/¨<))
(↕2˘)/¨<      Powerset (as a length-dimensional tensor)
(⥊        )    Deshape tensor to single dimension
((⍷∾)¨          )  Concatenate, remove dupes in each element
∘                    Then...
/⊢                       filter the input by...
(⌈´¬⌊´)                               whether range (span)...
=                              is equal to...
≠                             length...
({          }¨    )                     for each element.


Originally had 34 bytes but there was a bug.

Arturo, 57 bytes

$=>[select--powerset&[[]]=>[b:flatten&[][email protected]\0max<=b]]  Try it $=>[                  ; a function
select            ; select elements from
--powerset&[[]]   ; powerset of input without empty set
=>[               ; begin select, assign current elt to &
b:flatten&    ; flatten sets in current elt
[]=           ; is the empty block equal to
--            ; set difference of
@             ; evaluate block
..            ; range
b\0           ; first element of b
max<=         ; max of b
b             ; and b (second argument to set difference)
]                 ; end select
]                     ; end function


Julia 1.0, 66 bytes

!l=all(diff(sort([l...;])).<2) ? l : maximum(i->!setdiff(l,[i]),l)


Try it online!

Python 3.8 (pre-release), 84 bytes

f=lambda a:max(f(a-{i})for i in a)if a and~-len(b:={*sum(a,())})-max(b)+min(b)else a


Try it online!

Takes a set of tuples as input and recursively removes items until a valid result is found.