parameters: partition_1 (list / array) - a partitioning of a dataset
    according to some clustering method. Cluster labels are arbitrary.
    partition_2 (list / array) - another partitioning of the same dataset.
    Labels don't need to match, nor do the number of clusters.

    subfunctions: get_membership( parameter partition (list / array) )
    returns a list of length equal to the number of clusters found in the
    partition. Each element is the set of members of the cluster. Ordering
    is arbitrary.

    variables used: t = total number of points in the dataset m1 = cluster
    memberships from partition_1 m2 = cluster memberships from partition_2
    l1 = length (i.e. number of clusters) of m1 l2 = length of m2 entropy_1
    = Shannon entropy of partition_1 entropy_2 = Shannon entropy of
    partition_2 mut_inf = mutual information of partitions prob1 =
    probability distribution of partition 1 - i.e. the probability that a
    randomly chosen datapoint belongs to each cluster (size of cluster /
    size of dataset) prob2 = as above, for partition 2 intersect = number of
    common elements in partition 1 [i] and partition 2 [j]

def entropies(partition_1, partition_2):
    """ parameters: partition_1 (list / array) - a partitioning of a dataset
    according to some clustering method. Cluster labels are arbitrary.
    partition_2 (list / array) - another partitioning of the same dataset.
    Labels don't need to match, nor do the number of clusters.

    subfunctions: get_membership( parameter partition (list / array) )
    returns a list of length equal to the number of clusters found in the
    partition. Each element is the set of members of the cluster. Ordering
    is arbitrary.

    variables used: t = total number of points in the dataset m1 = cluster
    memberships from partition_1 m2 = cluster memberships from partition_2
    l1 = length (i.e. number of clusters) of m1 l2 = length of m2 entropy_1
    = Shannon entropy of partition_1 entropy_2 = Shannon entropy of
    partition_2 mut_inf = mutual information of partitions prob1 =
    probability distribution of partition 1 - i.e. the probability that a
    randomly chosen datapoint belongs to each cluster (size of cluster /
    size of dataset) prob2 = as above, for partition 2 intersect = number of
    common elements in partition 1 [i] and partition 2 [j] """

    if partition_1.num_elements() != partition_2.num_elements():
        print('Partition lists are not the same length')
        return 0
    else:
        total = partition_1.num_elements()

    m1 = partition_1.get_membership()
    m2 = partition_2.get_membership()
    l1 = len(m1)
    l2 = len(m2)
    entropy_1 = 0
    entropy_2 = 0
    mut_inf = 0
    for i in range(l1):
        prob1 = len(m1[i]) / total  # float division ensured by __future__ import
        entropy_1 -= prob1 * np.log2(prob1)
        for j in range(l2):
            if i == 0:  # only calculate these once
                prob2 = len(m2[j]) / total
                entropy_2 -= prob2 * np.log2(prob2)
            intersect = len(set(m1[i]) & set(m2[j]))
            if intersect == 0:
                continue  # because 0 * log(0) = 0 (lim x->0: xlog(x)->0)
            else:
                mut_inf += intersect / total * np.log2(total * intersect
                                                       / (len(m1[i]) * len(m2[j])))

    return entropy_1, entropy_2, mut_inf