Define this algorithm: slots and pins

Question

I have several slots and pegs arranged in a straight line. The pegs can be moved and they need to be moved to each slot. The slot can be left empty only if all the bindings are made. When a snap moves, he is not allowed to pass another snap. In other words, the order of the pegs must be maintained. Preferably, the total distance moved by all the pins should be kept to a minimum. If possible, the binding should be located in the nearest available slot.

All I want to know: what field of mathematics is dealing with such a problem? What are the names of known algorithms that have similar problems? I am looking for Google feed. Some keywords.

+--oooo-+--+---+---o--+------+--+-ooo+o-+-------o--+-----oo-+-o + - Slots o - Pegs 

EDIT: I think this visualization makes more sense. These are two separate tracks that need to be lined up.

 Slots: +-------+--+---+------+------+--+----+--+----------+---------+-- Pegs: ---oooo------------o--------------ooo-o---------o--------oo---o 

EDIT: I just want to make it clear that the number of slots can be more or less than the number of pegs.

Answer 1

I think this is a classic feed for dynamic programming . In fact, see “sequence alignment,” which may be another good search term on this wikipedia page.

Key Understanding:

Imagine that you have bindings as a list of snap positions (peg1: more pegs) and slots as a list of slot positions (slot1: more slots). Cause this problem (peg1: pegs, slot1: slots). Then the solution is either peg1 in slot 1, or a solution (pins, slots), or it is a solution (peg1: pegs, slots).

This gives a recursive definition of how to solve it.

Or in pseudocode (written in the style of functional programming), imagine the distance of a function (snap, slot):

 distance([]) = 0 distance((peg,slot):matches) = distance(peg,slot)+distance(matches) solution(peg:[], slot:[]) = [(peg,slot)] solution(peg:pegs, slot:slots) = if distance(a)<distance(b) then a else b where a = solution(peg:pegs, slots) and b=(peg,slot):solution(pegs, slots) 

This solution should be more efficient by combining distance into a data structure.

Answer 2

I don’t know where this problem came from, but I’m sure that this is a form of combinatorial optimization , and more specifically, which can be solved using (integer) linear programming .

Answer 3

“the total distance moved by all pegs should be kept at least”

If I am missing something, this is not a problem.

Since the binding order must be supported, you can simply copy the bindings 1, 2, 3, ...

+ - 1234 - + - + --- + --- 5 - + ------ + - + - 678 + 9 - + ------- 10 - + ----- 11-12 - + - 13

and the final state should be binding 1 in slot 1, pin 2 in slot 2, etc.

+ - 1 - + - 2 - + - 3 - + - 4 - + - 5 - + - 6 - + - 7 - + - 8 - + - 9 - + - 10 - + - 11 - + - 12 - + - 13 - +

The inability to jump the pins against each other does not matter, each binding should move at a certain distance from it, starting from its end point. As long as all the moves are in the right direction, and the binding never has to back up , then the distance that each individual binding should move is a simple constant (it does not depend on the order of the moves), and the sum of these distances, your cost function is also constant.

I do not see the need for dynamic programming or the problem of optimizing linear programming.

If you enter a cost for selecting a binding and set it, then perhaps there is a problem of optimization, but even this can be trivial.

Change in response to 1800 Information Comment

This is true only if the number of slots is equal to the number of pegs - this was not assumed in the problem expression - 1800 INFORMATION (2 hours ago)

Ok, I missed it. Thank you for pointing out that I am missing. I'm still not sure if this is rocket science.

Suppose # pegs> # hole. Calculate the final state as above, as if you had extra holes; then select N pegs that were moved on and remove them from the problem: those that are not moving. Reprogram, ignoring these bindings.

Assume # hole> # pegs. The correct final state may or may not have spaces. Calculate the final state as described above and see where the neighboring snaps have moved to each other. These are the moments where you can break it down into subtasks that can be solved trivially. There is another variable when you have holes at both ends of the adjacent subtask - where the final continuous sequence begins.

Yes, this is a little more complicated than I thought at first, but still it seems that a little work with pencil and paper should show that the solution is a couple of understandable and encoded cycles.

Answer 4

combinatorics. Combinatorial Algorithms Concrete math. (Also the title is an excellent and relevant book by Donald Knuth.

Answer 5

If the number of codes == the number of slots, there is only one solution. The first pin MUST go to the first slot, the next pin MUST go to the next slot, etc.

The numbers are different from each other, then they are a little more complicated, because the binding or slot (no matter which one we can move) can be moved to many places.

Brute force: Assume that the number of objects is m pegs and n slots (interchangeably), m <n

• For each path (nm), slots can be (see some combinatorics algorithms to see how to do this)
  • There (nm) the selected slots will be empty.
  • Fill all remaining slots with codes. Calculate the distance traveled. This becomes the same as in the case discussed above.
• Choose a location with a minimum travel distance.

Recursive solution:

  int solve(int pegs, int *peg_x, int slots, int *slot_x) { if (slots > pegs ) return solve(slots, slot_x, pegs, peg_x); if (slots == 0 || pegs==0) return 0; // Cannot move int option1 = INT_MAX, options2 = INT_MAX; if (pegs > slots ) // Can try skipping a peg option1 = solve(pegs-1, peg_x+1 /* Move over one element */ slots, slot_x); // pegs >= slots option2 = solve(pegs-1, peg_x+1, slots-1, slot_x+1) + abs(peg_x[0]-slot_x[0]); return min(option1, option2); } 

This solution still requires storing the results in a table, so no subtask will be solved several times to be a dynamic solution.

Thinking .... will be updated .....

Answer 6

Theory of rest or mathematics ...