2
$\begingroup$

I want to solve the following problem:

You have a list of numbers, for example [10, 33, 7, 7, 12].

The goal is to find the permutation of this list that maximizes the function $\sum_i a_{i-1} a_i a_{i+1}$, where indices are cyclic (taken modulo the number of elements).

My initial thought was to simply sort the list by descending order and put the second element at the end, but this doesn't work always. Can you suggest an optimal strategy?

EDIT:

My big problem is that i don't get why this is a hard problem. I get that there is an exponential number of permutations, but why simply sorting the values isn't enough ?

I tried implementing an A star:

  • each node contains two lists: a list of already placed values and a list of the others that are left. for example the root will be [], [10, 33, 7, 7, 12] and a final node [7,7,33,12,10], []
  • the children of a node are computed as follows: take a member of the second list and insert at the end of the first list. the root will have 5 different children.
  • now the most important part: how to evaluate each node: $F(node) = G(node) + H(node)$
    • I evaluate the first list using the fitness function: $G$
    • Find the highest possible value for $a_{i−1} \times a_i \times a_{i+1}$ in the second list and multiply it by the size of the same list: $H$

This finds the optimal solution but performance-wise it's even worse than the naive algorithm.

$\endgroup$
  • $\begingroup$ (In case you don't see this:) This site works differently from others you might be used to. We're not a discussion forum. Please don't use the 'answer' box to post anything other than an answer to your question. If you want to clarify the question, the way to do that is to click the 'edit' link under your question and revise the question to what it should have been from the start. I'll make that change for you this time, but in the future please do this yourself. Thank you! $\endgroup$ – D.W. Dec 30 '17 at 6:24
  • $\begingroup$ It looks like you accidentally created multiple accounts. Please register your account to make sure you retain access -- this will let you post comments and edit your question -- and I suggest you merge your two accounts. See cs.stackexchange.com/help/merging-accounts for instructions on how to do that. $\endgroup$ – D.W. Dec 30 '17 at 6:25
  • $\begingroup$ What's the source where you ran across this question? What does this have to do with Prolog? And, what did you try? Which algorithm design paradigms have you tried? Have you tried to build a dynamic programming algorithm? A greedy algorithm? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Dec 30 '17 at 6:26
  • $\begingroup$ "why simply sorting the values isn't enough". The objective is to find a permutation which maximizes the function. After sorting, you won't be sure that whether the permutation will lead to maximum value. In other words, you need not sort, since it won't lead to optimal answer. $\endgroup$ – kiner_shah Dec 31 '17 at 14:46
  • $\begingroup$ I think the optimal solution is to start with the highest number and put the next highest number alternatingly on the total left and the total right. [7,12,33,10,7] $\endgroup$ – Albert Hendriks Jan 1 '18 at 15:22

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.