Tuples by sequentially stepping through entries in list of lists

Question

Challenge:

Given a list of nonempty lists of integers, return a list of tuples of the following form: First list tuples starting with each element of the first list followed by the first element of every subsequent list, so the ith tuple should be [ith element of first list, first element of second list, ... , first element of last list]. For example:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [[1, 4, 7], [2, 4, 7], [3, 4, 7], ...

Then do tuples of the form [last element of first list, ith element of second list, first element of third list, ..., first element of last list], so in our example this would be:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] =>  ..., [3, 4, 7], [3, 5, 7], [3, 6, 7], ...

Continue on with each remaining list, until you get to [last element of first list, ..., last element of second to last list, ith element of last list]:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] => ..., [3, 6, 7], [3, 6, 8], [3, 6, 9]]

The full output is as follows:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] => 
        [[1, 4, 7], [2, 4, 7], [3, 4, 7], [3, 5, 7], [3, 6, 7], [3, 6, 8], [3, 6, 9]]

Some boilerplate for good measure:

• If you want the input to be lists of strings, or lists of positive integers, it's fine. The question is about manipulating lists, not about what is in the lists.
• Input and output can be in any acceptable format.
• Either a full program or function is permitted.
• Standard loopholes are disallowed by default.
• This question is code golf, so lowest byte-count wins.

Examples:

[] => [[]] (or an error, thanks to ngn for correcting the output in this case)

[[1]] => [[1]]

[[1, 2], [3, 4], [5]] => [[1, 3, 5], [2, 3, 5], [2, 4, 5]]

[[1], [2], [5, 6], [3], [4]] => [[1, 2, 5, 3, 4], [1, 2, 6, 3, 4]]

[[1, 2, 3], [4, 5]] => [[1, 4], [2, 4], [3, 4], [3, 5]]

[[1, 2, 3], []] => unspecified behavior (can be an error)

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

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

If anyone has a better title, let me know.

Answer 1

JavaScript (ES6), 59 bytes

Expects a list of lists of positive integers.

f=a=>[a.map(a=>a[0]),...a.some(a=>a[1]&&a.shift())?f(a):[]]

Try it online!

How?

At each iteration:

• We output a new list consisting of the first element of each list.
• We remove the first element of the first list containing at least 2 elements, and repeat the process. Or we stop the recursion if no such list exists.

Answer 2

Python 2, 72 bytes

f=lambda a:zip(*a)[:1]+(any(len(u)>1and u.pop(0)for u in a)and f(a)or[])

Try it online!

This is a Python port of Arnauld's excellent Javascript algorithm.

Answer 3

Python 2, 62 bytes

lambda M:[zip(*M)[l.pop(0)*0]for l in M+[[1,1]]for _ in l[1:]]

Try it online!

Using Chas Brown's pop idea inspired by Arnauld's JS submission.

---

Python 2, 68 bytes

M=input()
for l in[[0,0]]+M:
 for x in l[1:]:l[0]=x;print zip(*M)[0]

Try it online!

Mutates the first elements of the lists to hold the desired values. The [[0,0]]+ is an ugly hack to print the initial first values.

Answer 4

Jelly, 15 bytes

ẈṚṪ×€PƊƤFQṚCịŒp

Try it online! (the footer displays the actual returned list rather than a Jelly representation)

How?

Indexes into the Cartesian product of the lists at the required points...

ẈṚṪ×€PƊƤFQṚCịŒp - Link: list of lists  e.g. [[6,8,4,9],[7,1,5],[3,2]]
Ẉ               - length of each            [4,3,2]
 Ṛ              - reverse                   [2,3,4]
       Ƥ        - for each prefix:             [2]      [2,3]      [2,3,4]
      Ɗ         -   last 3 links as a monad:
  Ṫ             -     tail (pop rightmost)     2        3          4
     P          -     product (of remaining)   1        2          6
    €           -     for €ach (range tail)    [1,2]    [1,2,3]    [1,2,3,4]   
   ×            -       multiply               [1,2]    [2,4,6]    [6,12,18,24]
        F       - flatten                   [1,2,2,4,6,6,12,18,24]
         Q      - de-duplicate              [1,2,4,6,12,18,24]
          Ṛ     - reverse                   [24,18,12,6,4,2,1]
           C    - complement (1-x)          [-23,-17,-11,-5,-3,-1,0]
             Œp - Cartesian product (of the input)
                -         -> [[6,7,3],[6,7,2],[6,1,3],[6,1,2],[6,5,3],[6,5,2],[8,7,3],[8,7,2],[8,1,3],[8,1,2],[8,5,3],[8,5,2],[4,7,3],[4,7,2],[4,1,3],[4,1,2],[4,5,3],[4,5,2],[9,7,3],[9,7,2],[9,1,3],[9,1,2],[9,5,3],[9,5,2]]
            ị   - index into (1-based & modular)
                -   indexes:      -23,                                            -17,                                            -11,                                             -5,             -3,             -1,     0
                -    values: [[6,7,3],                                        [8,7,3],                                        [4,7,3],                                        [9,7,3],        [9,1,3],        [9,5,3],[9,5,2]]
                -         -> [[6,7,3],[8,7,3],[4,7,3],[9,7,3],[9,1,3],[9,5,3],[9,5,2]]

---

ẈṚ’ṣ1T$¦ƬUṚị"€ (14 bytes) fails for inputs with (non-trailing) length one lists; but maybe ṣ1T$ can be replaced with something else?

Answer 5

APL (Dyalog), 15 bytes (SBCS)

Thanks ngn for pointing out an unnecessary byte

{∪⌈\,⍉⍳≢¨⍵}⊃¨¨⊂

Try it online!

{∪⌈\,⍉⍳≢¨⍵} generates lists to index into the input. e.g (1 2 3) (4 5 6) (7 8 9) -> (0 0 0) (1 0 0) (2 0 0) (2 1 0) (2 2 0) (2 2 1) (2 2 2)

≢¨⍵: the length of each list in the input

,⍉⍳ creates all combinations of numbers up to it's input. e.g. 2 3 -> (0 0) (1 0) (0 1) (1 1) (0 2) (1 2)

⌈\: scan with maximum. e.g. the above example would now be (0 0) (1 0) (1 1) (1 1) (1 2) (1 2)

∪: remove duplicates

⊃¨¨⊂ does the indexing, being mindful of the depth of either argument

Answer 6

Haskell, 87 bytes

x?[]=[]
x?([c]:d)=(x++[c])?d
x?((c:d):e)=(x++c:map head e):x?(d:e)
f x=[]?x++[last<$>x]

Try it online

Answer 7

K (ngn/k), 40 21 19 18 17 bytes

{x@'/:?|\+|!|#'x}

Try it online!

uses ideas from @H.PWiz's answer

{ } function with argument x

#' length of each

| reverse

! all index tuples for an array with those dimensions as columns in a matrix (list of lists)

| reverse

+ transpose

|\ running maxima

? unique

x@'/: use each tuple on the right as indices in the corresponding lists from x

Answer 8

Charcoal, 33 bytes

ＩＥ⊕ΣＥθ⊖ＬιＥθ§λ⌈⟦⁰⌊⟦⊖Ｌλ⁻ι∧μΣＥ…θμ⊖Ｌν

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

Ｉ

Cast the integers to strings before implicitly printing using the default output format for lists, which is each item on its own line, and nested lists double-spaced.

Ｅ⊕ΣＥθ⊖Ｌι

Take the sum of the lengths of the lists and subtract the length of the list of lists. Then loop from 0 to this value inclusive.

Ｅθ§λ

Map over the list of lists and index into each list.

⌈⟦⁰⌊⟦⊖Ｌλ

Clamp the index to 0 and the last index in the list. (The closing brackets are implied.)

⁻ι∧μΣＥ…θμ⊖Ｌν

After the first list, subtract the decremented lengths of all the previous lists from the outermost index. (This doesn't work for the first list because the length of lists is empty and the sum isn't a number.)

Answer 9

Python 2, 91 bytes

f=lambda a,p=():a and[p+(q,)+zip(*a)[0][1:]for q in a[0][p>():]]+f(a[1:],p+(a[0][-1],))or[]

Try it online!

Answer 10

APL (Dyalog Classic), 32 30 27 bytes

1↓¨∪⊃{(⍵,¨⊃⍺),⍺,¨⍨⊢/⍵}/⌽0,⎕

Try it online!

complete program, input is from the keyboard (⎕)

for input [] outputs [[]] (their APL equivalents are 0⍴⊂⍬ and ,⊂⍬)

assumes uniqueness of numbers in the input

Answer 11

JavaScript (ES6), 58 54 bytes

h=(x,s)=>[x.map(y=>s|y?y[0]:s=y.shift()),...s?h(x):[]]

After 14+ attempts at golfing my code down (removing all instances of while loops, push, and concat), I arrived at an iteration algorithmically similar to @Arnauld's answer, unsurprising given how succinct it is!

Accepts a list of lists of positive integers. Try it online!

58 bytes

For 1 more byte, replacing s = y.shift() with y.shift(s = 1) should handle all integers (presumably, as I have not personally tested it).

h=(x,s)=>[x.map(y=>!s/y[1]?s=y.shift():y[0]),...s?h(x):[]]

58 bytes

Bonus version, with slight rearranging:

h=x=>[x.map(y=>s&&y[1]?y.shift(s=0):y[0],s=[]),...s||h(x)]

Explanation

Early versions of the code tried to modify a clone of (an array of) the first elements of each array, but the extra step of initializing that array was expensive... until I realized that mapping over the first elements of each array was roughly the "only" operation necessary if I mutate the original arrays.

Uses a boolean flag to check if any array has been shifted (i.e. shortened) yet. Golfed the conditional check down further by observing that JS coerces arrays with a number value as its only element into that number, while coercing arrays with multiple values as NaN.

var
h = (x, s) => 
    [
        x.map(y =>                 // map to first element of each array
            s|y                    // if s == 1 (i.e. an array has been shortened)
                                   // or the current array y has length == 1
                ? y[0]
                : s = y.shift()    // remove first element of y and set s to truthy
        ),
        ...s ? h(x) : []           // only concatenate a recurrence of the function if an array has had a value removed
    ]