Issues with understanding Dining table optimal seating algorithm

Question

I was reading through a problem and was trying to solve this problem.

You've invited N people over for dinner. Let's say 4.

You have a circular dinner table and you wish to seat everyone around it. Unfortunately, not all of your friends are friends with each other, but you'd like to seat everyone optimally so that as many people as possible are seated next to people they consider friends and not enemies.

You've charted everyone's friendships and hatreds in a matrix of size NxN and represented friendships with the integer 1, hatreds with -1, and sheer indifference with 0.

[[ 0, 1, 1, 1, 1],    ← yes you like all your friends
 [-1, 0, 1,-1, 0],
 [-1, 1, 0, 1, 0],
 [ 1, 1, 1, 0,-1],
 [ 1, 0, 0,-1, 0]]

Question:

-> Write a Javascript method that computes an optimal seating arrangement as an Array, e.g. [0,4,2,1,3], for a given input matrix. (assuming indexes 0 and N-1 are seated adjacently). What is the time complexity for the solution? Add thoughts on possible optimizations.

I've tried solving this manually however, I didn't understand the question's example [0,4,2,1,3] for the given input matrix.

Can someone Enlighten me?

How did he/she come up with [0,4,2,1,3]?

Thanks and very much appreciate your time.

Answer 1

How did he/she come up with [0,4,2,1,3]?

That permutation certainly isn't the right answer for the example input (see reasoning below), so I think that Emma's comment above is spot-on: the problem statement is just demonstrating what a "seating arrangement as an Array" should look like in general, not specifically demonstrating the optimal seating arrangement for the example input.

---

As for why I say that [0,4,2,1,3] certainly isn't the right answer for the example you've given . . . I don't completely understand how we decide whether one permutation is better than another, but it's clear that [0,4,1,2,3] is better by any measure. For both [0,4,2,1,3] and [0,4,1,2,3], the first person (0) likes both neighbors; the second person (4) is neutral toward both neighbors; and the third and fifth people (2 and 3 in the former, 1 and 3 in the latter) each like one neighbor and are neutral toward the other. The only difference between the two permutations is that in [0,4,2,1,3], the fourth person (1) is neutral toward one neighbor and dislikes the other, whereas in [0,4,1,2,3], the fourth person (2) is neutral toward one neighbor and likes the other. So the latter is obviously superior, no matter whether we consider it more important to increase likes or to decrease dislikes.