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

Posted by programmingpraxis
Filed in Exercises
16 Comments »

16 Responses to “Alternating Lists”

  1. V said
    February 1, 2019 at 12:51 PM

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

    def alternate(*lists)
  head, *tail = lists
  head.zip(*tail).flatten.compact
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
    February 1, 2019 at 4:56 PM

    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
    February 2, 2019 at 9:24 AM

    — 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
    February 2, 2019 at 10:06 PM

    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
    February 3, 2019 at 1:44 AM

    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
    February 3, 2019 at 6:23 AM

    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
    February 3, 2019 at 6:54 AM

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

  8. matthew said
    February 3, 2019 at 7:37 AM

    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
    February 3, 2019 at 8:09 AM

    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
    February 3, 2019 at 8:05 PM

    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
    February 8, 2019 at 1:40 AM

    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[1];
  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
    February 8, 2019 at 2:22 AM

    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
    February 8, 2019 at 6:36 AM

    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
    February 10, 2019 at 1:20 AM

    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[1];
  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
    February 10, 2019 at 6:44 AM

    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
    February 13, 2019 at 8:12 PM 
    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]

Leave a comment