Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
Group formation


Let me first discuss different algorithmic approaches.

First approach: We may mimic the algorithm we we typically carry out physically: Calculate the number of groups k = n / gs. Then count in the following way: 1, 2, 3, ... , k, 1, 2, 3, ... k, .... (a total of n times), and for each counting, point at a person. This ensures an optiomal distribution. A challenge, however, is to grab each student while counting. It may be an idea to form a list of pairs (person . groupnumber), and to reorganize this list before returning the result. Here is function based on this idea:

(define (grouping group-size person-list)
  (let* ((number-of-groups (quotient (length person-list) group-size))) ; distribute remainders on these, avoiding small or singleton groups.
     (if (< (length person-list) group-size)  ; very few participators...
         #f
         (let* ((group-numbers (number-interval 1 number-of-groups))
                (large-enough-group-number-list (replicate-to-length group-numbers (length person-list)))
                (group-alist (pair-up (shuffle-list person-list) large-enough-group-number-list)))
           (take-out-groups number-of-groups group-alist)))))

(define (take-out-groups number-of-groups group-alist)
  (take-out-groups-from 1 number-of-groups group-alist))

(define (take-out-groups-from i number-of-groups group-alist)
  (if (<= i number-of-groups)
      (let ((group-i (filter (lambda (e) (= (cdr e) i)) group-alist)))
        (cons (map car group-i) 
              (take-out-groups-from (+ i 1) number-of-groups group-alist)))
      '()))

Notice that the solution above makes use of the non-R5RS function number-interval, replicate-to-length, and shuffle-list. Strictly speaking, filter is non-standard as well. You can find all of these functions in the LAML and Scheme Browser, in the 'General LAML Library' category (follow the link to Scheme source files).

Second approach: Make a list of group sizes, such as (m1 m2 m3 ... mk) that represent an equal distribution. (Many/some of these numbers will typically be gs). Then write a recursive function that takes m1 persons from the group, reduce the input list with m1 elements, and recurse with (m2 m3 ... mk). Here is a possible function:

(define (grouping group-size person-list)
  (let* ((distribution (distribute-integer-in-sum-parts (length person-list) (quotient (length person-list) group-size))))  
    (group-according-to-distribution (shuffle-list person-list) distribution)))

; Return a list of number-of-parts integers that sums up to n.
(define (distribute-integer-in-sum-parts n number-of-parts)
  (let ((base-number (quotient n number-of-parts))
        (rest (remainder n number-of-parts)))
    (append (make-list rest (+ base-number 1))
            (make-list (- number-of-parts rest) base-number))))  


(define (group-according-to-distribution person-list distribution)
   (if (null? distribution)
       '()
       (cons (list-prefix person-list (car distribution))
             (group-according-to-distribution (list-tail person-list (car distribution)) (cdr distribution)))))

In this solution, the function list-prefix is a solution to another exercise.

Randomness may be handled by a list shuffle function. If is does not already exists, it is relatively straight forward to program it with use a random (integer) number generator:

(define (shuffle-list lst)
   (if (null? lst)
       '()
        (let* ((lst-lgt (length lst))
               (random-el-number (random lst-lgt)) ; 0 .. (- lst-lgt 1)
               (selected-element (list-ref lst random-el-number))
               (rest-elements (list-but-ref lst random-el-number)))
          (cons selected-element 
                (shuffle-list rest-elements)))))

Functions that rely on random numbers are not referential transparent. They are not pure functions. So it is kind of problematic!

Notice how useful it is to represent part of the soution as intermediate lists. This is typical in list-based functional programming.