与理解餐桌最佳座位的算法问题

Question

我是通过阅读问题，并试图解决这个问题。

您邀请了N多人过来吃饭。比方说，4。

你有一个圆形的餐桌，你希望它周围坐的每一个人。不幸的是，并非所有的朋友彼此的朋友，但你希望让尽可能多的人可能都坐在旁边，他们考虑的朋友，而不是敌人的人以最佳容纳每一个人。

你已经绘制了大家的友谊和仇恨的尺寸为N×N的矩阵，代表友谊与整数1，用-1仇恨，并与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]]

题：

- >写，计算最佳的座椅布置为阵列的Javascript方法，例如[0,4,2,1,3]，对于给定的输入矩阵。 （假定索引0和N-1相邻地安置）。什么是解决方案的时间复杂度？在可能的优化添加的想法。

我试图解决这个手动不过，我不明白这个问题的例子[0,4,2,1,3]对于给定的输入矩阵。

有人可以告诉我吗？

怎么他/她拿出[0,4,2,1,3]

谢谢，非常感谢您的时间。

Answer 1

怎么他/她拿出[0,4,2,1,3]

那排列肯定是不适合的例子中输入正确的答案（见下面的推理），所以我认为上述Emma的评论是点上：问题描述只是展示了“座椅布置为一个数组”应该是什么样子的一般情况下，没有特别的展示为例如输入的最优座位安排。

---

至于我为什么说，[0,4,2,1,3]肯定不是你给出的例子是正确的答案。 。 。我不完全理解我们是如何决定一个置换是否比另一种好，但很明显，[0,4,1,2,3]是由任何措施好。对于这两种[0,4,2,1,3]和[0,4,1,2,3]，第一人（0）都喜欢的邻居;第二人（4）是朝向与两个相邻中性;并且第三和第五人（在后者的2和3在前者中，1和3）的每个像一个相邻且朝向另一中性。两个排列之间的唯一区别是，在[0,4,2,1,3]，第四人（1）是朝向一个邻近中性和不喜欢的其它，而在[0,4,1,2,3 ]，第四人（2）是朝向一个邻近中性和喜欢其他。因此，后者显然优越，无论我们是否认为更重要的是增加喜欢或减少不喜欢。

Answer 2

检查所有可能的顺序是，即使有可能是这一特定问题的更有效的算法经典的置换任务。

一种优化可以通过减少由于在例如圆形的订单置换到阵列长度-1来完成0,1,2,3,4和4,0,1,2,3（以及所有进一步旋转）是相同的。从你自己的座位总是开始于位置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);

})();

输出：

[ [ 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 ] ] ]

正如我们所看到的，还有被颠倒排列与（0）具有相同的评价，当然你自己组合。 Eleminating镜像命令，即颠倒排列，则是另一种优化。

我这样做是为了在单步演示有面临一个问题，一步一步一个更可读的代码。您可以直接重构评级计算入置换算法。

正确计算的时间复杂度似乎并不那么容易。请阅读在下面的意见的讨论。