# Tuples by sequentially stepping through entries in list of lists

## 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.

• I have a feeling that [] => [] should really be [] => [[]] but can't find the words to explain why.
– ngn
Commented Jul 14, 2018 at 18:21
• @ngn You are right, it should be [[]] because there is a single empty tuple with one entry from each of the (zero) sublists. Probably it's too annoying to require programs to correctly output this, so I'll say that it's not necessary.
– Hood
Commented Jul 14, 2018 at 20:26
• Yes [] is, strictly speaking, an empty list of non-empty lists but the output is ambiguous between [] and [[]]if it's an allowed input. ("First list tuples starting with each element of the first list..." - there is no first list, so we are done -> []) Commented Jul 14, 2018 at 20:28
• @JonathanAllan I'm now convinced that the "correct" output for [] should be [[]]. For instance, the number of output tuples is sum(inner list lengths) - length of outer list + 1 which in the empty case gives 1, which is the length of [[]] but not the length of []. This is a bit of a pedantic issue though...
– Hood
Commented Jul 14, 2018 at 20:32
• Can we assume all the entries are distinct? Or, more strongly, a permutation on 1..n like in your examples?
– xnor
Commented Jul 14, 2018 at 21:50

# 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.
• That a.some trick is awesome! Commented Jul 14, 2018 at 15:36
• @ETHproductions Now looking for a challenge where using awe.some would not be a waste of bytes... :) Commented Jul 15, 2018 at 11:33

# 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.

# 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.

# 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?

# 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

• Great answer! You beat me by almost half my bytes. ⊆ seems unnecessary.
– ngn
Commented Aug 4, 2018 at 16:39
– ngn
Commented Aug 4, 2018 at 16:47
• @ngn Nice, I can't remember what caused me to think it was. Thanks! Commented Aug 4, 2018 at 16:58

# Haskell, 87 bytes

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


Try it online

# 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

# 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.)

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

# APL (Dyalog Classic), 3230 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

• Not that it makes a difference to the output, but I think the input for the second test should be ,⊂,1 Commented Jul 15, 2018 at 19:28
• @H.PWiz that's right, fixed, cheers
– ngn
Commented Jul 16, 2018 at 4:22

# 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
]