This is related to a real-world problem I'm solving but I'm keeping it abstract so I don't bog you down with details. An efficient answer to this feels like it should be obvious but I'm not seeing it. Let me know if there's a better place to ask this.
Given some letters and some numbers, I need to generate the most efficient letter-number pairing.
letters: a-z
numbers: 0-99
result: {a:46, b:27, c:13, ...}
For each of the C(26,2)=325 letter pairs, there exists a frequency of how likely it is for that letter pair to occur. Ex: {'th': 0.03}
For each of the C(100,2)=4950 number pairs, there exists a cost for how expensive it is to transition between those two numbers. Ex: {(32,17): 53}
Pair each number with a letter, such that the total cost of all letter combinations (frequency*cost) is as low as possible.
Hopefully this makes sense. Is there some elegant way to do this that doesn't involve brute-forcing the solution?
This is an instance of the quadratic assignment problem, which is a generalization of the traveling salesman problem. It is difficult to solve large instances optimally, but using an integer linear programming solver will generally perform much better than brute force.