对具有重叠的偏好列表进行排序/创建排名

Question

我正在搜索以下问题的简单算法/javascript实现：

我有一个具有以下结构的对象：

preference = {1:4,2:3,3:2,4:1}

该对象表示四个人（1,2,3,4）关于他们是否决定第一、第二、第三或最后的偏好。

在这种情况下，这很简单：人 1 想走在最后 (4)，人 2 想去第三 (3)，人 3 想排在第二位 (2)，第 4 个人想先走 (1)

然而，人们也可能有相同/重叠的偏好，例如：

preference = {1:1,2:1,3:1,4:1} // everybody wants to first
preference = {1:1,2:1,3:4,4:4} // some want to go first, some want to go last

然而，只有一个人可以占据链中的一个位置——不能有任何重叠。在这种情况下，需要根据以下规则重新分配顺序：

假设两个人想先走，两个人想走第二；

– 然后，随机决定谁先走的顺序。 'winner'可以先走，另一个走第二

– 因为现在第二名也被拿走了，所以在所有原本想要第二名的人中随机确定第三名。获胜者可以第三名，另一名最后一名

最后，我需要一个根据这些规则分配顺序的对象；例如

偏好 = {1:1,2:3,3:3,4:1} –> final_order = {1:1,2:3,3:4,4:2}

你知道在 javascript 中实现这种算法的简单方法吗？（伪代码也可以帮助我！）

Answer 1

您可以收集想要的首选项并通过遍历所有位置对首选项重新排序。

与preference共

{ 1: 1, 2: 3, 3: 3, 4: 1 }

temp 有此内容

[
    undefined, /* sparse */
    [
        1,
        4
    ],
    undefined, /* sparse */
    [
        2,
        3
    ]
]

下面的迭代省略了 spars 元素，只访问了两个数组。

并且由于随机选择，结果是不可预测的，但顺序是想要的。

function adjustPreference(preference) {
    let temp = [],
        t = 1;
    
    for (let i = 1; i < 5; i++) {
        (temp[preference[i]] = temp[preference[i]] || []).push(i);
    }
    
    temp.forEach(persons => {
        while (persons.length) {
            const random = persons.splice(Math.floor(Math.random() * persons.length), 1)[0];
            preference[random] = t++;
        }
    });
    
    return preference;
}

console.log(adjustPreference({ 1: 1, 2: 3, 3: 3, 4: 1 }));

对具有重叠的偏好列表进行排序/创建排名

ordering / creating a ranking of a list of preferences with overlaps

javascript

sorting

ranking