Greedy algorithms

greedyAlgorithms.py

'''Course: https://www.coursera.org/learn/algorithmic-toolbox#about'''


def getLargestNumber(numberList):
    '''given a sequence of digits,
    this function prints out the largest number that consists of those digits'''

    print("\nsequence of digits given: ", numberList)
    largestNumList = []
    while numberList:
        maxNum = max(numberList)
        largestNumList.append(maxNum)
        numberList.remove(maxNum)

    print("largest number sequence that consists of those digits: ", largestNumList, "\n")





def getMinimumNumberOfRefillsForCars(distToStationsList, numOfStations, distWithFullTank):

    '''distToStationsList contains origin, distances to gas stations from origin, destination.
    This function prints out minimum number of times car would need to visit fuel stations before
    running out of fuel'''

    numberOfRefills = 0
    currentRefill = 0

    while currentRefill <= numOfStations:
        lastRefill = currentRefill

        while ((currentRefill <= numOfStations) and
            (distToStationsList[currentRefill + 1] - distToStationsList[lastRefill] <= distWithFullTank)):
            currentRefill += 1

        if currentRefill == lastRefill:
            print("Impossible to reach any gas station")

        if currentRefill <= numOfStations:
            numberOfRefills += 1

    print("Number of refills for car: ", numberOfRefills, "\n")






def partitions(aList):  #TODO: see how this recursive function works and can it be made to look simpler?
    '''taken from
    https://stackoverflow.com/questions/30130053/how-find-all-groups-of-subsets-of-set-a-set-partitions-in-python
    This function is used in groupingChildrenIntoGroupsSlow function'''

    if not aList:
        yield []
    else:
        a, *R = aList
        for partition in partitions(R):
            yield partition + [[a]]
            for i, subset in enumerate(partition):
                yield partition[:i] + [subset + [a]] + partition[i+1:]



def groupingChildrenIntoGroupsSlow(childrenAgesList, maxAgeGap):
    '''this function returns minimum number of groups that satisfy maxAgeGap
    very slow approach'''

    minNumberOfGroups = len(childrenAgesList)

    for partition in partitions(childrenAgesList):

        satisfiesConstraint = True
        numOfGroups = len(partition)
        for i in range(numOfGroups):

            if max(partition[i]) - min(partition[i]) > maxAgeGap:
                satisfiesConstraint = False

        if satisfiesConstraint:
            minNumberOfGroups = min(minNumberOfGroups, numOfGroups)

    print("Minimum number of groups Slow: ", minNumberOfGroups)







def groupingChildrenIntoGroupsFast(childrenAgesList, maxAgeGap):
    '''this function returns minimum number of groups that satisfy maxAgeGap
        very fast approach'''

    minNumberOfGroups = 0
    i = 0
    childrenAgesList.sort()
    numOfChildren = len(childrenAgesList)

    while i < numOfChildren:

        maxAgeForGroup = childrenAgesList[i] + maxAgeGap
        i += 1
        minNumberOfGroups += 1

        while i < numOfChildren and childrenAgesList[i] <= maxAgeForGroup:
            i += 1

    print("Minimum number of groups Fast: ", minNumberOfGroups)






def fractionalKnapsack(weightsList, priceList, maxCapacity):
    '''maximizes the total value of items that can fit in a knapsack/bag
    slower approach'''

    assert len(weightsList) == len(priceList), "weightsList and valuesList should be of same length"

    numOfItems = len(weightsList)
    amountList = [0] * numOfItems
    totalValue = 0

    valueList = [priceList[i]/weightsList[i] for i in range(numOfItems)]

    for i in range(numOfItems):

        maxValue = 0
        index = 0
        for j in range(numOfItems):
            if valueList[j] >= maxValue and weightsList[j] > 0:
                index = j

        amountOfItem = min(weightsList[index], maxCapacity)
        totalValue += amountOfItem * valueList[index]
        weightsList[index] -= amountOfItem
        maxCapacity -= amountOfItem
        amountList[index] += amountOfItem

    print("\nAmount of items taken Slow: ", amountList, " with max total value: ", totalValue)






def sortedFractionalKnapsack(weightsList, priceList, maxCapacity):
    '''maximizes the total value of items that can fit in a knapsack/bag
    faster approach'''

    assert len(weightsList) == len(priceList), "weightsList and valuesList should be of same length"

    numOfItems = len(weightsList)
    amountList = [0] * numOfItems
    totalValue = 0

    valueList = [priceList[i]/weightsList[i] for i in range(numOfItems)]
    sortedIndices = sorted(range(numOfItems), key=lambda x: valueList[x], reverse=True)

    for i in range(numOfItems):
        if maxCapacity == 0:
            print("Amount of items taken Fast: ", amountList, " with max total value: ", totalValue)
            return

        amountOfItem = min(weightsList[sortedIndices[i]], maxCapacity)
        totalValue += amountOfItem * valueList[sortedIndices[i]]
        weightsList[sortedIndices[i]] -= amountOfItem
        maxCapacity -= amountOfItem
        amountList[sortedIndices[i]] += amountOfItem

    print("Amount of items taken Fast: ", amountList, " with max total value: ", totalValue)





if __name__ == '__main__':

    getLargestNumber(numberList=[5, 7, 3, 9, 1, 9])

    getMinimumNumberOfRefillsForCars(distToStationsList=[0, 200, 375, 550, 750, 950], numOfStations=4, distWithFullTank=400)

    groupingChildrenIntoGroupsFast(childrenAgesList=[1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9], maxAgeGap=1)
    groupingChildrenIntoGroupsSlow(childrenAgesList=[1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9], maxAgeGap=1)

    fractionalKnapsack(weightsList=[4, 3, 2], priceList=[20, 18, 14], maxCapacity=7)
    sortedFractionalKnapsack(weightsList=[4,3,2], priceList=[20,18,14], maxCapacity=7)