# Is there a better algorithm for ordering inputs to minimise cost of alignment

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()
``````

As no responses in two months, I have posted a £256 bounty for a solution on freelancer.