COS126

• Download ShannonEntropy.java

/******************************************************************************
 *  Name:    Reference Solution
 *  NetID:   ref
 *  Precept: P00
 *
 *  Description:  Reads two integers m and n from standard input; then reads
 *                a sequence of n integers between 1 and m from standard input;
 *                and prints the Shannon entropy of the sequence to standard
 *                output.
 *
 ******************************************************************************/

public class ShannonEntropy {

    public static void main(String[] args) {

        // sequence of n integers are between 1 and m
        int m = StdIn.readInt();

        // number of integers
        int n = StdIn.readInt();

        // compute frequencies
        // freq[i] = # times integer i appears
        int[] freq = new int[m+1];
        for (int j = 0; j < n; j++) {
            int value = StdIn.readInt();
            freq[value]++;
        }

        // compute Shannon entropy
        double entropy = 0.0;
        for (int i = 1; i <= m; i++) {
            double p = 1.0 * freq[i] / n;
            if (freq[i] > 0)  
                entropy -= p * Math.log(p) / Math.log(2);
        }

        // print results
        StdOut.println(entropy);
    }
}