## Alternating Lists

### February 1, 2019

Today’s exercise is a simple task in list manipulation:

Write a program that takes one or more lists and returns a single list containing the elements of the input lists, taken alternately from the lists. If the lists are of different lengths, continue taking items from the lists that remain.

For instance, given the inputs `(1 2 3 4 5)`, `(a b c)` and `(w x y z)`, the desired output is `(1 a w 2 b x 3 c y 4 z 5)`.

Your task is to write a program to take items alternately from multiple lists. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 16 Responses to “Alternating Lists”

1. V said

In Ruby. Assumes elements are in the lists are not nil.

```def alternate(*lists)
end

print alternate([1,2,3,4,5], ["a","b","c"], ["w","x","y","z"])

# outputs
# [1, "a", "w", 2, "b", "x", 3, "c", "y", 4, "z", 5]
```
2. Steve said

Mumps version

```
LISTS(LISTS) ;

S MAX=0 F I=1:1:\$L(LISTS,"|") S LEN=\$L(\$P(LISTS,"|",I),";"),MAX=\$S(LEN>MAX:LEN,1:MAX)

S LIST=""

F J=1:1:MAX F I=1:1:\$L(LISTS,"|") S CHAR=\$P(\$P(LISTS,"|",I),";",J) S:CHAR'="" LIST=LIST_CHAR_" "

Q \$E(LIST,1,\$L(LIST)-1)
```

w \$\$LISTS^ZZJSG(“1;2;3;4;5|a;b;c|w;x;y;z”)

1 a w 2 b x 3 c y 4 z 5

3. matthew said

— Here’s some Haskell, I’ll leave it to enthusiasts to convert to pointfree style.

```-- Interleave elements from a list of lists.
-- Corecursive so works with infinite lists.
interleave s = aux (filter (not . null) s) where
aux [] = []
aux s = map head s ++ interleave (map tail s)

-- Specialize to Int to avoid problems with []
iinterleave = interleave :: [[Int]] -> [Int]

main =
print (iinterleave [[],[]]) >>
print (iinterleave [[1,2,3],[]]) >>
print (iinterleave [[],[1,2,3]]) >>
print (iinterleave [[1,2,3],[4,5,6]]) >>
print (iinterleave [[1,2,3],[4,5,6],[7,8,9]]) >>
print (take 10 (iinterleave [[1,4..],[2,5..],[3,6..]]))
```
4. Paul said

In Python.

```from itertools import zip_longest

sentinel = object()

def alt_lists(*lists):
return [xi for x in zip_longest(*lists, fillvalue=sentinel)
for xi in x if xi is not sentinel]

print(alt_lists([1,2,3,4,5], ["a", "b", "c"], ["w", "x", "y", "z"]))
```
5. Hugo Costa said

I think my solution is a bit simpler:

(define (alternate x . y)
(cond
((null? y) x)
((null? x)
(apply alternate y))
(else
(cons
(car x)
(apply
alternate
(append y (list (cdr x))))))))

6. Globules said

Here’s another Haskell solution. (In pointfree style! :-)

```{-# OPTIONS_GHC -fno-warn-type-defaults #-}

import Data.List (transpose)

alternate :: [[a]] -> [a]
alternate = concat . transpose

main :: IO ()
main = do
-- From the original problem.
print \$ alternate [['1', '2', '3', '4', '5'],
['a', 'b', 'c'],
['w', 'x', 'y', 'z']]

-- From matthew's solution.
print \$ alternate [[], [] :: [()]]
print \$ alternate [[1, 2, 3], []]
print \$ alternate [[], [1, 2, 3]]
print \$ alternate [[1, 2, 3], [4, 5, 6]]
print \$ alternate [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print \$ take 10 \$ alternate [[1, 4..], [2, 5..], [3, 6..]]
```
```\$ ./alternating
"1aw2bx3cy4z5"
[]
[1,2,3]
[1,2,3]
[1,4,2,5,3,6]
[1,4,7,2,5,8,3,6,9]
[1,2,3,4,5,6,7,8,9,10]
```
7. matthew said

@Globules: very nice – it would be good to have a pointfree definition of transpose as well!

8. matthew said

Here’s another Haskell version, this one is a simplification of a modification of the Haskell library definition of transpose. I’ve not seen that list comprehension with partial matches idiom before:

```interleave               :: [[a]] -> [a]
interleave []             = []
interleave xss = [h | (h:_) <- xss] ++ interleave [ t | (_:t) <- xss]
```
9. matthew said

And here’s a pointfree Haskell solution that doesn’t seem too incomprehensible:

```heads = map head . filter (not . null)
tails = map tail . filter (not . null)
interleave = concatMap heads . takeWhile (not . null) . iterate tails
```
10. Tim said

Here’s an simple-minded scheme solution with filter and map:

(define (not-null? x) (not (null? x)))

(define (splice . lists)
(let ((flists (filter not-null? lists)))
(if (not-null? flists)
(append (map car flists)
(apply splice (map cdr flists)))
'())))

11. Daniel said

Here’s a solution in C that uses linked lists.

```#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
char* val;
struct node* next;
} node_t;

void print_list(node_t* list) {
while (list != NULL) {
printf("%s", list->val);
if (list->next != NULL)
printf("->");
list = list->next;
}
printf("\n");
}

void free_list(node_t* list) {
while (list != NULL) {
node_t* next = list->next;
free(list);
list = next;
}
}

void alternate(node_t** lists, int n, node_t** output) {
node_t* list = NULL;
int done = 0;
while (!done) {
done = 1;
for (int i = 0; i < n; ++i) {
if (lists[i] == NULL) continue;
done = 0;
node_t* node = malloc(sizeof(node_t));
node->val = lists[i]->val;
node->next = list;
list = node;
lists[i] = lists[i]->next;
}
}
node_t* prev = NULL;
node_t* node = NULL;
node_t* next = list;
while (next != NULL) {
prev = node;
node = next;
next = next->next;
node->next = prev;
}
list = node;
*output = list;
}

int main(int argc, char* argv[]) {
int n = 0;
int capacity = 1;
node_t** lists = malloc(sizeof(node_t*) * capacity);
node_t* list = NULL;
char* sep = argv;
for (int i = argc - 1; i >= 1; --i) {
char* arg = argv[i];
if (!strcmp(sep, arg)) {
if (list == NULL) continue;
++n;
if (n > capacity) {
capacity *= 2;
lists = realloc(lists, sizeof(node_t*) * capacity);
}
lists[n - 1] = list;
list = NULL;
continue;
}
node_t* node = malloc(sizeof(node_t));
node->next = list;
node->val = arg;
list = node;
}
for (int i = 0; i < n / 2; ++i) {
node_t* tmp = lists[i];
lists[i] = lists[n - i - 1];
lists[n - i - 1] = tmp;
}
node_t* alternating = NULL;
alternate(lists, n, &alternating);
print_list(alternating);
for (int i = 0; i < n; ++i) {
free_list(lists[i]);
}
free_list(alternating);
free(lists);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out . 1 2 3 4 5 . a b c . w x y z
1->a->w->2->b->x->3->c->y->4->z->5
```
12. Sathya Sundaram said

Here’s a more raw, packageless python implementation I thought of:

def alternator(lists):
max_len = 0

``````for l in lists:
length = len(l)
if length > max_len:
max_len = length
else:
pass

alt_list = []

for i in range(max_len):
for l in lists:
try:
alt_list.append(l[i])
except :
pass

print(alt_list)
``````

if name == “main“:
lists = [[1,2,3,4,5],[‘a’,’b’,’c’],[‘w’,’x’,’y’,’z’]]
alternator(lists)

13. Daniel said

Here’s a solution in Common Lisp.

```(defun alternate (&rest lists)
(labels ((rec (result lists)
(let ((lists (remove-if #'null lists)))
(if (null lists)
result
(rec (reduce #'(lambda (a b) (cons b a))
(mapcar #'car lists)
:initial-value result)
(mapcar #'cdr lists))))))
(reverse (rec (list) lists))))
```

Example.

```CL-USER> (alternate '(1 2 3 4 5) '(a b c) '(w x y z))
(1 A W 2 B X 3 C Y 4 Z 5)
```
14. Daniel said

Here’s a solution in C that uses arrays.

```#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define INIT_CAPACITY 1

typedef struct array {
int n;
char** data;
} array_t;

void print_array(array_t* array) {
printf("[");
for (int i = 0; i < array->n; ++i) {
if (i > 0) printf(" ");
printf("%s", array->data[i]);
}
printf("]\n");
}

void alternate(array_t* arrays, int n, array_t* output) {
output->n = 0;
for (int i = 0; i < n; ++i)
output->n += arrays[i].n;
output->data = malloc(sizeof(char*) * output->n);
int col = 0; // index in input data (column of jagged array)
int idx = 0; // index in output data
while (idx < output->n) {
for (int i = 0; i < n; ++i) {
if (col >= arrays[i].n) continue;
output->data[idx++] = arrays[i].data[col];
}
++col;
}
}

int main(int argc, char* argv[]) {
char* sep = argv;
int n = 0;
for (int i = 1; i < argc; ++i)
if (!strcmp(sep, argv[i])) ++n;
array_t* arrays = malloc(sizeof(array_t) * n);
int capacity = INIT_CAPACITY;
for (int i = 0; i < n; ++i) {
arrays[i].n = 0;
arrays[i].data = malloc(sizeof(char*) * capacity);
}
int pos = 0;
for (int i = 2; i < argc; ++i) {
if (!strcmp(sep, argv[i])) {
++pos;
capacity = INIT_CAPACITY;
continue;
}
++(arrays[pos].n);
if (arrays[pos].n > capacity) {
capacity *= 2;
arrays[pos].data = realloc(arrays[pos].data, sizeof(char*) * capacity);
}
arrays[pos].data[arrays[pos].n - 1] = argv[i];
}
array_t alternating;
alternate(arrays, n, &alternating);
print_array(&alternating);
for (int i = 0; i < n; ++i)
free(arrays[i].data);
free(arrays);
free(alternating.data);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out . 1 2 3 4 5 . a b c . w x y z
[1 a w 2 b x 3 c y 4 z 5]
```
15. Daniel said

Here’s a solution in Python.

```def alternate(l):
l = [list(reversed(x)) for x in l]
output = []
while l:
l = [x for x in l if x]
for x in l:
output.append(x.pop())
return output

l = [[ 1 ,  2 ,  3 ,  4,  5],
['a', 'b', 'c'],
['w', 'x', 'y', 'z']]

print(alternate(l))
```

Output:

```[1, 'a', 'w', 2, 'b', 'x', 3, 'c', 'y', 4, 'z', 5]
```
16. Steve said
```Klong version (Does not handle empty list for list entry)
Code:

f::{[r l2]; r::x; l2::[]; {r::r,*x; l2::l2,(,(1_x))}'y; (,r),(,l2)}

g2::{[t]; :[0=+/#'y;x;g2((t::f(x;y))@0; t@1)]}

g::{g2([]; x)}

Output:

{.p(x," --> ",g(x))}'[[[1 2 3 4 5] ["a" "b" "c"] ["W" "X" "Y" "Z"]] [[]
[]] [[1 2 3] []] [[] [1 2 3]] [[1 2 3] [4 5 6]] [[1 2 3] [4 5 6] [7 8 9]] [[1 4
5 6 7 8 9 10 11 12] [2 5 6 7 8 9 10 11 12] [3 6 7 8 9 10 11 12 13 14]]]

[[1 2 3 4 5] [a b c] [W X Y Z]  -->  1 a W 2 b X 3 c Y 4 Z 5]
[[] []  --> ]
[[1 2 3] []  -->  1 2 3]
[[] [1 2 3]  -->  1 2 3]
[[1 2 3] [4 5 6]  -->  1 4 2 5 3 6]
[[1 2 3] [4 5 6] [7 8 9]  -->  1 4 7 2 5 8 3 6 9]
[[1 4 5 6 7 8 9 10 11 12] [2 5 6 7 8 9 10 11 12] [3 6 7 8 9 10 11 12 13 14]  -->  1 2 3 4 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10 11 12 11 12 13 12 14]

```