javascript - Issues with understanding Dining table optimal seating algorithm - Stack Overflow

admin管理员组

文章数量:1317742

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 putes 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 plexity 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 e up with [0,4,2,1,3]?

Thanks and very much appreciate your time.

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 putes 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 plexity 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 e up with [0,4,2,1,3]?

Thanks and very much appreciate your time.

• javascript
• algorithm
• data-structures

Share Improve this question Follow edited Feb 4, 2019 at 0:23 SFer asked Feb 3, 2019 at 23:44 SFerSFer 10911 silver badge44 bronze badges 13

• 1 You are row and column 0, you like all your friends, but only your friends 2 and 3 like you, "friends" 1 and 2 dislike you (-1 in column 0 - that's your own popularity). The expample means the sitting order: You, next to you friend 4, then 2, 1, 3 which is on the other side next to you. – Pinke Helga Commented Feb 4, 2019 at 0:03
• 3 The problem statement seems too vague; if the goal is that "as many people as possible are seated next to people they consider friends and not enemies", how do we quantify that? For example: suppose that one arrangement has each guest adjacent to one person they like and one person they hate, and a different arrangement has each guest adjacent to two people they're neutral about. Which of these is considered better? – ruakh Commented Feb 4, 2019 at 0:04
• 2 @ruakh sure. I'm guessing its an open ended question. Can you make an assumption and e up with a possible oute? – SFer Commented Feb 4, 2019 at 0:25
• 3 I'm not sure if I want to have dinner with these folks, not if my first two "friends" don't like me back! – Scott Sauyet Commented Feb 4, 2019 at 0:45
• 2 Incidentally, this problem is NP-hard, by reduction from the Hamiltonian cycle problem, so you're unlikely to find an efficient solution for large numbers of guests. – user2357112 Commented Feb 4, 2019 at 3:14

 |  Show 8 more ments

2 Answers 2

Sorted by: Reset to default 4

How did he/she e 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 ment 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 pletely 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.

Checking all possible orders is a classical permutation task even if there might be a more efficient algorithm for this specific problem.

One optimization can be done by reducing the permutation to array length-1 since in circular orders e.g. 0,1,2,3,4 and 4,0,1,2,3 (and all further rotations) are the same. You can view the order from you own seat always starting at position 0.

(function ()
{
  'use strict';

  let popularity =
  [
    [ 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],
  ];

  function permutation(arr)
  {
    let
      l = arr.length,
      perms = []
    ;

    if(l<2)
      return [arr];

    for(let i=0; i<l; i++)
    {
      let
        cpy    = Array.from(arr),
        [perm] = cpy.splice(i, 1)
      ;
      perms.push(...permutation(cpy).map(v => [perm, ...v]));
    }

    return perms;
  }


  let
    keys = Array.from(popularity.keys()).slice(1),
    permutations = permutation(keys),
    rating = permutations.map(v =>
    {
      let
        last = v.length -1,

        // start with our own relationships to the left and right neighbour
        // (each: we like him, he likes us)
        rate =
            popularity [0]       [v[0]]
          + popularity [v[0]]    [0]
          + popularity [0]       [v[last]]
          + popularity [v[last]] [0]
      ;

      for(let i = 0; i<last; i++)
        rate += popularity[v[i]][v[i+1]] + popularity[v[i+1]][v[i]];

      return [rate, [0, ...v]];
    }
  ).sort( (v1, v2) => ( v1[0] === v2[0] ? 0 : (v1[0] > v2[0] ? -1 : 1))  );

  console.log(rating);

})();

output:

[ [ 8, [ 0, 4, 1, 2, 3 ] ],
  [ 8, [ 0, 3, 2, 1, 4 ] ],
  [ 6, [ 0, 3, 1, 2, 4 ] ],
  [ 6, [ 0, 4, 2, 1, 3 ] ],
  [ 4, [ 0, 1, 4, 2, 3 ] ],
  [ 4, [ 0, 1, 2, 3, 4 ] ],
  [ 4, [ 0, 4, 1, 3, 2 ] ],
  [ 4, [ 0, 1, 3, 2, 4 ] ],
  [ 4, [ 0, 2, 3, 1, 4 ] ],
  [ 4, [ 0, 3, 2, 4, 1 ] ],
  [ 4, [ 0, 4, 2, 3, 1 ] ],
  [ 4, [ 0, 4, 3, 2, 1 ] ],
  [ 2, [ 0, 3, 4, 2, 1 ] ],
  [ 2, [ 0, 3, 1, 4, 2 ] ],
  [ 2, [ 0, 2, 4, 1, 3 ] ],
  [ 2, [ 0, 4, 3, 1, 2 ] ],
  [ 2, [ 0, 3, 4, 1, 2 ] ],
  [ 2, [ 0, 1, 2, 4, 3 ] ],
  [ 2, [ 0, 2, 1, 4, 3 ] ],
  [ 2, [ 0, 2, 1, 3, 4 ] ],
  [ 0, [ 0, 1, 4, 3, 2 ] ],
  [ 0, [ 0, 2, 3, 4, 1 ] ],
  [ -2, [ 0, 1, 3, 4, 2 ] ],
  [ -2, [ 0, 2, 4, 3, 1 ] ] ]

As we can see, there still are reversed permutations bined with yourself (0) having the same rating of course. Eleminating mirrored orders, i.e. reversed permutations, would be another optimization.

I did this for demonstration in single steps to have a more readable code facing single problems step by step. You could refactor the rating calculation directly into the permutation algorithm.

Properly calculating the time plexity does not seem to be that easy. Please read the discussion in the ments below.

本文标签： javascriptIssues with understanding Dining table optimal seating algorithmStack Overflow