My dad who works as a technician described to me a problem with a very combinatorial flavor to it. Suppose you had a set of widgets with a left side and a right side, where each side has a measure of offset attached to it. When you arrange two widgets side by side, you get a score computed by the difference between offsets of the widgets. So for two widgets, you can get two possible scores depending on how you arrange them. When you add in N widgets to the mix, the number of possible combinations goes way up. The question is whether there is an efficient algorithm that can return a sequence of widgets such that the net score between all the adjacent widgets is constrained below a given threshold, or better yet, minimized.
My first impression of the problem is the naive approach and factorial run time. Actually, this brute force approach involves calculating through permutations, which isn’t very intuitive how to implement, I think. There is a C++ algorithm function called next_permutation, which generates the next lexicographic permutation from some given sequence, which *is* intuitive to use: just wire it up into a loop and keep track of the best one.
A problem that seems similarly put is the knapsack problem, which tries to maximize a primary value given a secondary constraint.
It’s an interesting problem and I will look more into it.
