## Alternating Lists

### February 1, 2019

This is simple enough:

```(define (alternate . xss)
(let loop ((xss xss) (zs (list)))
(cond ((null? xss) (reverse zs))
((null? (car xss)) (loop (cdr xss) zs))
(else (loop (append (cdr xss) (list (cdar xss)))
(cons (caar xss) zs))))))```

The only trick is the expression `(list (cdar xss))`, where the `list` is required to keep the data structure as a list of lists. Here’s the example problem, with added output to show what is happening inside the loop:

```> (alternate '(1 2 3 4 5) '(a b c) '(w x y z)) ((1 2 3 4 5) (a b c) (w x y z)) () ((a b c) (w x y z) (2 3 4 5)) (1) ((w x y z) (2 3 4 5) (b c)) (a 1) ((2 3 4 5) (b c) (x y z)) (w a 1) ((b c) (x y z) (3 4 5)) (2 w a 1) ((x y z) (3 4 5) (c)) (b 2 w a 1) ((3 4 5) (c) (y z)) (x b 2 w a 1) ((c) (y z) (4 5)) (3 x b 2 w a 1) ((y z) (4 5) ()) (c 3 x b 2 w a 1) ((4 5) () (z)) (y c 3 x b 2 w a 1) (() (z) (5)) (4 y c 3 x b 2 w a 1) ((z) (5)) (4 y c 3 x b 2 w a 1) ((5) ()) (z 4 y c 3 x b 2 w a 1) (() ()) (5 z 4 y c 3 x b 2 w a 1) (()) (5 z 4 y c 3 x b 2 w a 1) () (5 z 4 y c 3 x b 2 w a 1) (1 a w 2 b x 3 c y 4 z 5)```

You can run the program at https://ideone.com/qt9FQ7.

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]

```