Frequency Counts

March 8, 2019

Geeks For Geeks gives two solutions. The first one scans the array, accumulating the negative of the count at the index location of the array item, changing seen items to zero:

(define (freq vec)
  (let ((n (vector-length vec)))
    (let loop ((i 0))
      (cond ((= i n) (do ((j 0 (+ j 1))) ((= j n))
                       (when (negative? (vector-ref vec j))
                         (display (+ j 1)) (display " ")
                         (display (- (vector-ref vec j))) (newline))))
            ((not (positive? (vector-ref vec i))) (loop (+ i 1)))
            (else (let ((idx (- (vector-ref vec i) 1)))
                    (cond ((positive? (vector-ref vec idx))
                            (vector-set! vec i (vector-ref vec idx))
                            (vector-set! vec idx -1)
                            (loop i))
                          (else (vector-set! vec idx
                                  (- (vector-ref vec idx) 1))
                                (vector-set! vec i 0)
                                (loop (+ i 1))))))))))
> (freq '#(2 3 3 2 5))
2 2
3 2
5 1

That works, but the logic is tricky (quickly: explain why one branch of the inner cond calls (loop i) while the other branch calls (loop (+ i 1))), and it destroys the contents of the array; it is possible to recreate the contents of the array, but not their original order. Here is the second solution:

(define (freq vec)
  (let ((n (vector-length vec)))
    (do ((i 0 (+ i 1))) ((= i n))
      (vector-set! vec i
        (- (vector-ref vec i) 1)))
    (do ((i 0 (+ i 1))) ((= i n))
      (vector-set! vec (modulo (vector-ref vec i) n)
        (+ (vector-ref vec (modulo (vector-ref vec i) n)) n)))
    (do ((i 0 (+ i 1))) ((= i n))
      (when (< n (vector-ref vec i))
        (display (+ i 1)) (display " ")
        (display (quotient (vector-ref vec i) n)) (newline)))
    (do ((i 0 (+ i 1))) ((= i n))
      (vector-set! vec i
        (+ (remainder (vector-ref vec i) n) 1)))
    (display vec) (newline))) ; show that vec is unchanged
> (freq '#(2 3 3 2 5))
2 2
3 2
5 1
#(2 3 3 2 5)

After redefining the data from 1→n to 0→n−1, this adds n at the index of each item in the array, so you can calculate the count and the original item in the array as the quotient and remainder on dividing by n. Very clever!

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

Advertisements

Pages: 1 2

5 Responses to “Frequency Counts”

  1. Milbrae said

    Python

    def freqcount(seq):
        c = [0] * (len(seq))
        for i in seq:
            c[i-1] += 1
        return c
    
    if __name__ == "__main__":
        data = [2, 3, 3, 2, 5]
        fc = freqcount(data)
        for i in range(len(data)):
            print ("%d -> %d" % (i+1, fc[i]))
    
  2. Milbrae said

    Another Python, not sure about big-O though:

    from collections import Counter
    
    if __name__ == "__main__":
        data = [2, 3, 3, 2, 5]
        fc = Counter(data)
        for i in range(len(data)):
            print ("%d -> %d" % (i+1, fc.get(i+1, 0)))
    

    Output is
    1 -> 0
    2 -> 2
    3 -> 2
    4 -> 0
    5 -> 1

  3. Jan Van lent said

    Below a Python solution that satisfies the O(n) time and O(1) extra space requirement. It seems I came up with the first solution given. The second solution is indeed quite neat.

    import random
    
    n = 8
    a = [ random.randrange(n)+1 for i in range(n) ]
    print(a)
    # frequency count for checking purposes
    # this requires O(n) storage, so this is not a valid answer
    c = [0]*n
    for i in range(n):
        c[a[i]-1] += 1
    print(c)
    
    # move through the array
    # turn each entry a[i] into the negative of the count for the number i+1
    # in each step we either move to the next entry and/or increase the number
    # of entries that have become counts rather than numbers to be counted
    i = 0
    while i < n:
        if a[i] <= 0: # already a count, move on
            i = i + 1
        else: # number to be counted
            if a[i]-1 == i: # number is the position of its count
                a[i] = -1
            elif a[a[i]-1] > 0:
                # there is a number in the place where a[i]'s count should go
                # swap number to current place, update count and don't move on
                tmp = a[a[i]-1]
                a[a[i]-1] = -1
                a[i] = tmp
            else: # the entry for a[i] is already a count, update count, make current entry count and move on
                a[a[i]-1] -= 1
                a[i] = 0
                i = i + 1
    for i in range(n):
        a[i] = -a[i]
    print(a)
    print(a==c)
    
  4. Steve said
    
    Klong version
    
    :" $x - Change number to string; ?l - Returns unique elements in list l; l?x - Returns position(s) of element x in list l; #l?x - Returns count of positions of element x in list l; $#l?x - Returns string equivalent of count of positions of element x in list l"
    
    Code:
            freqcnts::{[l]; l::x; {.p(($x),": ",$#l?x)}'?l; :done}
    :monad
    
    Run:
            freqcnts([2 3 3 2 5])
    2: 2
    3: 2
    5: 1
    :done
            freqcnts([9 8 9 7 7 5 6])
    9: 2
    8: 1
    7: 2
    5: 1
    6: 1
    :done
    
    
  5. Daniel said

    Here are two solutions in C, each corresponding to one of the Geeks for Geeks methods.

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char* argv[]) {
      int n  = argc - 1;
      int* array = malloc(n * sizeof(int));
      for (int i = 0; i < n; ++i) {
        array[i] = atoi(argv[i + 1]);
      }
      int i = 0;
      while (i < n) {
        int x = array[i];
        if (x < 0) {
          ++i;
          continue;
        }
        if (array[x - 1] > 0) {
          array[i] = array[x - 1];
          array[x - 1] = -1;
          continue;
        }
        --array[x - 1];
        ++i;
      }
      for (int i = 0; i < n; ++i) {
        int count = array[i] < 0 ? -array[i] : 0;
        printf("%d: %d\n", i + 1, count);
      }
      free(array);
      return EXIT_SUCCESS;
    }
    
    int main(int argc, char* argv[]) {
      int n  = argc - 1;
      int* array = malloc(n * sizeof(int));
      for (int i = 0; i < n; ++i) {
        array[i] = atoi(argv[i+1]) - 1;
      }
      for (int i = 0; i < n; ++i) {
        array[array[i] % n] += n;
      }
      for (int i = 0; i < n; ++i) {
        printf("%d: %d\n", i + 1, array[i] / n);
      }
      free(array);
      return EXIT_SUCCESS;
    }
    

    Example Output (same for both program):

    $ ./a.out 1 3 5 7 9 1 3 5 7 9 1
    1: 3
    2: 0
    3: 2
    4: 0
    5: 2
    6: 0
    7: 2
    8: 0
    9: 2
    10: 0
    11: 0
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: