Output every sublist ... eventually

Question

You will be given as input an infinite stream of positive integers.

Your task is to write a program which outputs an infinite sequence of lists with two requirements:

• All lists in the output are finite sub-lists of the input stream.
• Every sub-list must be output eventually by your program.

Sub-lists are not necessarily contiguous, so [1,1] is a sub-list of [0,1,0,1,0,..., and should be included in your output if your input was [0,1,0,1,0,....

The empty list [] is a sub-list of every possible input, so it should always be output at some point.

Aside from this, you can do what you want. You can output them in whatever order suits you, you can output any sub-list any (positive) number of times. It's up to you to figure out what's best.

This is code-golf so answers will be scored in bytes with fewer bytes being the goal.

IO

Outputting an infinite sequence is done as per the defaults of the sequence tag wiki.

Input of an infinite sequence is basically the dual of those rules. You may:

• Take the input as a black-box function which takes \$n\$ and outputs the \$n\$th term
• Take the input as a black-box function which takes \$n\$ and outputs all terms up to the \$n\$th term
• Take the input as a lazy list, generator or stream.
• Take the input by repeatedly querying STDIN each time receiving the next term of the sequence.

Answer 1

Haskell, 31 27 bytes

-4 bytes thanks to Wheat Wizard!

Takes an infinite list as input and returns each finite sublist an infinite number of times.

f(a:l)=[]:do x<-f l;[a:x,x]

Try it online!

Answer 2

05AB1E, 1 byte

æ

Try it online!

05AB1E no builtin, 5 bytes

[DNÏ,

Try it online!

Takes the input as an 05AB1E infinite lazy list

[     infinite loop
 D    create a copy of the infinite list
 N    iteration index (starting from 0)
 Ï    elements of the list for which the corresponding element of the index is 1 
 ,    print

Answer 3

Python, 43 bytes

lambda s,n:[s(b)for b in range(n)if n>>b&1]

Attempt This Online!

Outputs the nth sublist.

Python, 55 bytes

n=0
while[print([s(b)for b in range(n)if n>>b&1])]:n+=1

Attempt This Online!

Takes input using a black-box function predefined under the name s, which takes a number and outputs the corresponding 0-indexed value of the sequence. Shown in the ATO link using the powers of 2 [1, 2, 4, 8, .... Outputs infinitely to STDOUT.

Uses the binary representation of each non-negative integer n to produce a sub-list; 1s in the binary representation correspond to indices where the list's value is included in the output.

A bug fix for -12 bytes (!):

By using n itself rather than the bit length of n to determine how many bits to select, we also get, pretty much for free, the ability to sometimes output sublists which don't include the first item.

Because n is always greater than or equal to its bit length (besides for 0), we will effectively select some 0 bits which form part of its "padding", but which allow us to skip some of the first few elements.

When n is 0, this is the only number with no 1s in its binary. As a result, by initialising n to 0, we output an empty list at the start, satisfying that requirement at no byte cost.

---

Python, ⁶³ 62 bytes

def f(s,*e):
 yield e
 for x in f(s,next(s)):yield from{x,e+x}

Attempt This Online!

This is a version based on @ovs' clever Haskell answer, but with some changes to make it work in Python where we don't have infinite lists. It might be improvable.

-1 thanks to Command Master

Thanks to loopy walt, this version now outputs every sub-list exactly once, for the same byte count.

Answer 4

Scala, 89 bytes

_.scanLeft(Seq[Int]())(_:+_)flatMap(l=>l.indices.toSet.subsets.map(_.toSeq.sorted map l))

Try it online!

Welp, this turned out much longer than I expected. Time to reconsider this approach. Input is a LazyList[Int]. It outputs all the sublists up to the current integer for every integer.

_                            //The input (infinite list)
.scanLeft                   //Scan left over the sequence,
  (Seq[Int]())(_:+_)        //building an infinite list of subsequences
flatMap(l=>                 //Map each of those subsequences l to its sublists
 l.indices.toSet.subsets   //Get all subsets of the indices
  .map(
   _.toSeq.sorted          //Sort the indices to ensure sublists are in order
   map l)                  //Map the index to the corresponding element in l
)

Answer 5

JavaScript (Node.js), 30 bytes

a=>n=>a(n).filter(_=>(n/=2)&1)

Try it online!

Input array as a function which output first n elements. Output n-th element.

Answer 6

R, 73 68 bytes

Or R>=4.1, 61 bytes by replacing the word function with a \.

Edit: -5 bytes thanks to @Giuseppe.

function(g)while(T<-T+1)for(i in 1:2^T)show(g(T)[!i%/%2^(T:1-1)%%2])

Try it online!

Explanation:

1. Take a black-box function g as an argument.
2. Increment T in each iteration - how many numbers to read from g.
3. In the loop, calculate all the sub-sequences of the current vector (and some more):
   • take all numbers from 1 to 2^T,
   • convert to binary,
   • use as logical indices, which numbers from g(T) to print.

Answer 7

[Ruby], 64 56 48 bytes

->g{1.step{|n|n.times{p *g[n].combination(_1)}}}

Attempt This Online!

• saved 8 Bucks thanks to @ovs

takes a black box function returning first n elements.

Answer 8

Charcoal, 21 bytes

ＷＳ«Ｅ⌕Ａ⮌⍘Ｌυ²1§υκＤ⎚Ｄ⊞υι

Try it online! Link is to verbose version of code. Explanation:

ＷＳ«

Repeatedly input the next integer as a string. (This will actually stop on a blank line, which is what I use to allow the linked example to halt, but for positive integers it will keep prompting for input.)

Ｅ⌕Ａ⮌⍘Ｌυ²1§υκ

Convert the length of the predefined empty list to binary and find the positions of the 1s counting the least significant bit as 0. Output the elements of the predefined empty list with matching positions.

Ｄ⎚Ｄ

Output the canvas double-spaced. (Charcoal's default output format lists one element per line, so it's not easy to distinguish consecutive lists otherwise, although if you were running it interactively then the Enter input: prompt would do the trick.)

⊞υι

Append the next term of the input stream to the predefined empty list.

Answer 9

Pari/GP, 35 bytes

g->i->[g(j)|j<-[0..i],bittest(i,j)]

Try it online!

Take the input as a black-box function which takes \$n\$ (0-indexed) and outputs the \$n\$th term.

Answer 10

Vyxal, 1 byte (non-competing)

ṗ

Try it Online!

Non-competing as this builtin and many others were recently given infinite list support because of this challenge.

Answer 11

Haskell + hgl, 2 bytes

sS

I just finished adding builtins having to do with subsequences to hgl. sS gets all the subsequences of the input and works just fine on infinite lists.

It outputs subsequences in order of the index of their last element last element. That is first it outputs the empty list, then it outputs all sequences that end in the 0th element, then all sequences that end in the 1st element, then all sequences that end in the 2nd etc.

Haskell + hgl, 21 bytes

jn<<mM(ap[i,p]<p)<+cg

Since it's no fun to just post a built-in here's one that solves the task without sS or related functions. First we make jn<<mM(ap[i,p]<p). This takes a finite list and outputs all subsequences.

To do this it uses mM, (mapM or traverse if you are a Haskell user) which is a little complicated, but it's equivalent to sQ<m (sequence.map if your a Haskell user) so I'll explain it like that.

First m(ap[i,p]<p) will replace every element with a list of a singleton containing itself and an empty list:

>>> m(ap[i,p]<p)[1,2,3]
[[[],[1]],[[],[2]],[[],[3]]]

Then sQ basically does the generalized cartesian product. It takes n lists as input and gives all the ways to take 1 item from each list. Since we have two possibilities in each list, the integer singleton or any empty list, this gives us basically binary numbers of n digits with 0 being the empty list and 1 being the value.

>>> mM(ap[i,p]<p)[1,2,3]
[[[],[],[]],[[],[],[3]],[[],[2],[]],[[],[2],[3]],[[1],[],[]],[[1],[],[3]],[[1],[2],[]],[[1],[2],[3]]]

Now we want to get rid of the singletons so we use m jn

>>> jn<<mM(ap[i,p]<p)$[1,2,3]
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

Now we have all the subsequences of the input! However this stalls out on infinite lists.

Our fix here is to use cg. cg gives all the contiguous subsequences of the input, possibly infinite. So we first run cg and then run this finite subsequence on every result.

Unlike the first solution this

Reflections

Nice to see that we used no 3 byte functions anywhere. Still

• ap[i,p]<p is a little long for my liking (<p)<ap could probably be it's own function. I think it would have use beyond this challenge.

Answer 12

Julia 1.0, ⁴⁵ 31 bytes

f\n=[f(i) for i=0:n if n&2^i>0]

Try it online!

Port of pxeger's answer. Outputs the n-th sublist

Julia 1.0, 45 bytes

!(x,a=[[]])=for i=x a=[@show a;vcat.(a,i)]end

Try it online!

Input is an iterator. Output has a bit of unnecessary stuff but hopefully it's acceptable

Answer 13

Pip -p, 18 bytes

lPBlW1P*lAL:_AEqMl

Reads values from stdin, outputs sublists to stdout. Each sublist will be printed infinitely many times. Attempt This Online!

Explanation

We track every sublist of the inputs-thus-far in l. At each iteration, we read a new input, append it to each of the existing sublists, append that list to the list of existing sublists, and output the whole thing.

lPBlW1P*lAL:_AEqMl
l                   Variable preset to empty list
 PBl                Push the empty list to l; l is now [[]]
    W1              While 1 (loop forever):
                Ml   Map this function to each sublist in l:
               q      Read a line of stdin
            _AE       and append it to the sublist
        lAL:         Append those results to l in-place
      P*             Print each sublist in l