1
$\begingroup$

I'm trying to sort the elements of a set of "goal" stacks to minimize the number of pushes/pops to reach each state. The inputs and outputs can be some other structure rather than stacks, they just represent a target state of the stack. Each goal must be reached in the order given in the input.

For example, given this input of goal stacks:

Input
[[9, 7, 6, 5, 4, 2],
 [9, 7, 6, 4, 3, 2, 1],
 [9, 7, 5, 5, 2, 1, 1],
 [9, 7, 6, 5, 2, 1],
 [9, 7, 6, 5, 3, 2]]

I want to produce an output like the following:

Output
[[9, 7, 2, 6, 4, 5],
 [9, 7, 2, 6, 4, 3, 1],  // 1 pop, 2 push
 [9, 7, 2, 5, 1, 5, 1],  // 4 pop, 4 push
 [9, 7, 2, 5, 1, 6],     // 2 pop, 1 push
 [9, 7, 2, 5, 6, 3]]     // 2 pop, 2 push
                         // 18 operations

I have tried sorting each list based on the common items in the next list, but without more look-ahead it produces a suboptimal solution. If I just sort based on the frequency distribution for all lists it also fails. Trying every permutation is the only approach that comes to mind.

Is there an efficient algorithm to correctly order the lists in this way?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.