Demo code to find the min average value from the subset of a positive integer set.

min_avg_subarray_v1.py

#!/usr/bin/env python3
#
# Author: Taihsiang Ho (tai271828) [email protected]
#
# Given an positive integer set Xi. The length of the set is n.
# Given arbitrary a and b, and 1 <= a < b <= n.
# Find the minimum average number, which is
# sigma(i=a to b) Xi / (b - a + 1)
#
#
# This version of solution is very straightforward, and thus has
# very high time and space complexity. For lower complexity,
# please refer to v2 and v3 version of the code.
#
# time complexity of get_min_avg_in_length: O(n^2)
#     We loop over
#         - range(0, len(set_whole) - length_subset + 1)
#             - sum(xset[a:b+1]) of get_avg
#         - get_min(avg_list).
#
# space complexity of get_min_avg_in_length: O(n)
#     We have to store data in the length of the whole set n.
#     (max avg_list length)
#


# x_set = {Xa, Xa+1, Xa+2, ..., Xb}
#x_set = [66, 77, 88, 99, 55, 44, 33, 22]
x_set = [10, 20, 30, 40, 50, 60, 70, 80]


def get_avg(xset, a, b):
    return sum(xset[a:b+1]) / float(b - a + 1)


def get_min(target_list):
    base = target_list[0]
    for element in target_list:
        if element < base:
            base = element

    return base


def get_min_avg_in_length(set_whole, length_subset):
    avg_list = []
    for index_a in range(0, len(set_whole) - length_subset + 1):
        index_b = index_a + length_subset - 1
        avg_a_b = get_avg(set_whole, index_a, index_b)
        avg_list.append(avg_a_b)

    local_min_avg = get_min(avg_list)

    print("Min Avg / Length: {} {}".format(local_min_avg, length_subset))

    return local_min_avg


def main(set_whole):
    min_avg_candidates = []
    for target_length in range(1, len(x_set) + 1):
        local_min_avg = get_min_avg_in_length(set_whole, target_length)
        min_avg_candidates.append(local_min_avg)

    avg_min = get_min(min_avg_candidates)

    print("The min average is {}".format(avg_min))


main(x_set)

min_avg_subarray_v2.py

#!/usr/bin/env python3
#
# Author: Taihsiang Ho (tai271828) [email protected]
#
# Given an positive integer set Xi. The length of the set is n.
# Given arbitrary a and b, and 1 <= a < b <= n.
# Find the minimum average number, which is
# sigma(i=a to b) Xi / (b - a + 1)
#
#
# This version of solution has the better time complexity performance
# compared to the version 1.
#
# time complexity of get_min_avg_in_length: O(n)
#     We loop over
#         - range(0, len(set_whole))
#         - range(length_subset, len(set_whole))
#
# space complexity of get_min_avg_in_length: O(n)
#     We have to store data in the length of the whole set n.
#     (max sum_list_subset length)
#


# x_set = {Xa, Xa+1, Xa+2, ..., Xb}
#x_set = [66, 77, 88, 99, 55, 44, 33, 22]
x_set = [10, 20, 30, 40, 50, 60, 70, 80]


def get_min(target_list):
    base = target_list[0]
    for element in target_list:
        if element < base:
            base = element

    return base


def get_min_avg_in_length(set_whole, length_subset):
    sum_list_subset = []
    sum_cumulative = 0
    for index in range(0, len(set_whole)):
        sum_cumulative += set_whole[index]
        sum_list_subset.append(sum_cumulative)

    local_min_avg = sum_list_subset[length_subset - 1] / float(length_subset)
    for index in range(length_subset, len(set_whole)):
        index_prev = index - length_subset
        sum_cumulative = sum_list_subset[index] - sum_list_subset[index_prev]
        new_avg = sum_cumulative / float(length_subset)
        local_min_avg = get_min([local_min_avg, new_avg])

    print("Min Avg / Length: {} {}".format(local_min_avg, length_subset))

    return local_min_avg


def main(set_whole):
    min_avg_candidates = []
    for target_length in range(1, len(x_set) + 1):
        local_min_avg = get_min_avg_in_length(set_whole, target_length)
        min_avg_candidates.append(local_min_avg)

    avg_min = get_min(min_avg_candidates)

    print("The min average is {}".format(avg_min))


main(x_set)

min_avg_subarray_v3.py

#!/usr/bin/env python3
#
# Author: Taihsiang Ho (tai271828) [email protected]
#
# Given an positive integer set Xi. The length of the set is n.
# Given arbitrary a and b, and 1 <= a < b <= n.
# Find the minimum average number, which is
# sigma(i=a to b) Xi / (b - a + 1)
#
#
# This version of solution has the best time and space complexity
# performance compared to the version 2 solution.
#
# time complexity of get_min_avg_in_length: O(n)
#     We loop over
#         - range(0, length_subset)
#         - range(length_subset, len(set_whole))
#
# space complexity of get_min_avg_in_length: O(1)
#     We coud store data in a constant, single space.
#     (sum_subset is an integer)
#

# x_set = {Xa, Xa+1, Xa+2, ..., Xb}
#x_set = [66, 77, 88, 99, 55, 44, 33, 22]
x_set = [10, 20, 30, 40, 50, 60, 70, 80]


def get_min(target_list):
    base = target_list[0]
    for element in target_list:
        if element < base:
            base = element

    return base


def get_min_avg_in_length(set_whole, length_subset):
    sum_subset = 0
    for index in range(0, length_subset):
        sum_subset += set_whole[index]

    local_min = sum_subset
    for index in range(length_subset, len(set_whole)):
        index_previous = index - length_subset
        sum_subset += set_whole[index] - set_whole[index_previous]
        local_min = get_min([local_min, sum_subset])

    local_min_avg = local_min / float(length_subset)
    print("Min Avg / Length: {} {}".format(local_min_avg, length_subset))

    return local_min_avg


def main(set_whole):
    min_avg_candidates = []
    for target_length in range(1, len(x_set) + 1):
        local_min_avg = get_min_avg_in_length(set_whole, target_length)
        min_avg_candidates.append(local_min_avg)

    avg_min = get_min(min_avg_candidates)

    print("The min average is {}".format(avg_min))


main(x_set)