I have written a solution to the following problem using permutations (factorial complexity?), but would like to know if a greedy or dynamic programming solution is possible. Would like to get some pointers in the right direction to get started on it. Is there an existing algorithm name for this and what complexity can I expect? Thanks.
Given some cumulative inputs lengths and their associated costs, and some cumulative output lengths aligned to those inputs, return an ordering of the inputs that minimises the costs of those inputs that span the breaks in aligned outputs.
from itertools import permutations
from bisect import bisect_left
def calcSplitCost(ins, splits):
cumulativeInputDepths = []
cumulativeValue = 0
print ('PERMUTATION', ins)
for vd in ins:
cumulativeValue += vd[0]
cumulativeInputDepths.append((cumulativeValue, vd[1]))
print ('CUMULATIVE', cumulativeInputDepths)
score = 0
for split in splits:
pos = bisect_left(cumulativeInputDepths, (split, ))
score += ins[pos][1]
print ('split', split, 'pos', pos, 'score', ins[pos][1])
return score
def sortInputsToMinimiseSplitCost(ins, outs):
outputSplits = []
t = 0
for out in outs[:-1]:
t += out
outputSplits.append(t)
print ('SPLITS', outputSplits)
print ('')
bestScore = None
bestPerm = None
for perm in permutations(ins):
score = calcSplitCost(perm, outputSplits)
if bestScore is None or score < bestScore:
bestPerm = perm
bestScore = score
print ('SCORE', score)
print ('')
print ('BEST SCORE', bestScore)
return bestPerm
def example1():
inputRangeCosts = [(100, 5),
(110, 30),
(120, 20)]
outputRanges = [150, 180]
# inputs outputs
# 100 150
# <-
# 210
# 330 330
# |
# BEST ((110, 30), (100, 5), (120, 20))
# best to put lowest cost 5 on the edges
bestInputOrder = sortInputsToMinimiseSplitCost(inputRangeCosts, outputRanges)
print ('BEST')
print (bestInputOrder)
def example2():
inputRangeCosts = [(10, 5),
(10, 6),
(10, 7),
(10, 8),
(10, 9),
(10, 10),
(10, 11)]
outputRanges = [21, 22, 27]
# inputs outputs
# 10
# 20 21
# <-
# 30
# 40 43
# <-
# 50
# 60
# 70 70
# | |
# BEST ((10, 7), (10, 8), (10, 5), (10, 9), (10, 6), (10, 10), (10, 11))
# best to put lowest costs 5 and 6 on the edges
bestInputOrder = sortInputsToMinimiseSplitCost(inputRangeCosts, outputRanges)
print ('BEST')
print (bestInputOrder)
if __name__ == '__main__':
example1()
example2()