在 JavaScript 中进行即时决选投票并增加选票

Question

我试图在 JavaScript 中实现 IRV，但我每 5 秒只能获得 10 对投票（仅用于开发测试），因此每次添加新的数组时添加到数组中是不切实际的一对选票到达客户。所以我想知道是否有任何方法可以在接收到数据时处理数据并与将要接收的新数据保持一致。

const candidates = ['candidate1', 'candidate2', 'candidate3'];

// I Will Receive more votes after 5 secs (or any in prod) that will replace this
let votes = [['candidate1', 'candidate3', 'candidate2'],
            ['candidate2', 'candidate1', 'candidate3'] /* etc*/];

// I Want to calculate the winner at the time
// But after 5 secs the array won't have the previous votes

我问的是当时有没有计算IRV Winner的算法，知道几秒后之前的值就没有了，无法正常计算。

有没有什么办法可以根据他们的位置给予分分，分值可以递增并且仍然是赢家？

这是我想出的办法，但它没有发挥应有的作用。但它应该能让您了解我需要什么。

// The Base Votes (only one for the demo)
let votes = [['candidate1', 'candidate3', 'candidate2']];

// Stores the Ranks Per Candidate
let ranked = [0, 0, 0];

// Calculates the IRV
function irv() {
    votes.forEach(vote => {
        let points = vote.length;

        vote.forEach((candidate, i) => {
            ranked[i] += points;
            points--;
        });
    });
}

// Calculate the Winner at the time
irv();

// Add new Votes
votes = [['candidate2', 'candidate1', 'candidate3']];

// ReCalculate the Winner
irv();

// Show the Winner
console.log(ranked);

在 IRV 之后，它应该给出候选人 1 和候选人 2 之间的平局，这种方法给我们候选人 1 作为获胜者。你能帮我解决这个问题或者给我一个可以解决这个问题的更好的算法吗？

Answer 1

这是一个（可能过于简单的）IRV 实现：

const irv = (ballots) => {
  const candidates = [... new Set (ballots .flat())]
  const votes = Object .entries (ballots .reduce (
    (votes, [v]) => {votes [v] += 1; return votes},
    Object .assign (... candidates .map (c => ({[c]: 0})))
  ))
  const [topCand, topCount] = 
    votes .reduce (([n, m], [v, c]) => c > m ? [v, c] : [n, m], ['?', -Infinity])
  const [bottomCand, bottomCount] = 
    votes .reduce (([n, m], [v, c]) => c < m ? [v, c] : [n, m], ['?', Infinity])

  return topCount > ballots .length / 2 
    ? topCand
    : irv (ballots .map (ballot => ballot .filter (c => c != bottomCand)) .filter (b => b.length > 0))
}

const ballots = [
  ['A', 'C', 'B', 'E', 'D'],
  ['B', 'D', 'A', 'F', 'G'],
  ['C', 'B', 'D'],
  ['B', 'D', 'E', 'A', 'H'],
  ['A', 'B', 'G', 'H', 'F'],
  ['G', 'E', 'B', 'H', 'D'],
  ['E', 'C', 'D', 'B', 'G'],
  ['A', 'B'],
  ['D', 'G'],
  ['F', 'E', 'C'],
  ['F', 'C', 'G', 'A', 'E'],
  ['B', 'C', 'G', 'A', 'E'],
  ['A', 'B', 'F', 'G'],
]

console .log (irv (ballots))

（请注意，根据我的评论，我不会尝试在调用之间保持任何特定状态。如果您需要累积选票，我建议单独进行，然后运行此函数当这些选票到达时。如果这太贵了，那么可以根据目前收到的选票运行按固定时间表进行。）

我们的选票只是一个有序的候选人选择列表。最后，我们通过依次淘汰 first-place 得票最少的候选人并将这些选票上剩余的候选人提高一位来选择候选人 B。

代码首先通过展平选票列表并选择集合中的所有唯一成员来收集候选人。然后我们计算每个候选人的第一名选票。这将采用 [["A", 4], ["C", 1],["B", 3], ["E", 1], ["D", 1], ["F", 2], ["G", 1], ["H", 0]] 格式，这使得在接下来的两个步骤中使用基于 reduce 的最小值和 max-choosers.[=35= 最容易找到顶部和底部候选者。 ]

这里的算法是天真的，通过简单地选择第一个具有该值的值来打破平局，这取决于投票顺序。一个完整的 IRV 系统会有比这更好的机制。

然后，最后，如果最高候选人的计数超过总计数的一半，我们 return 那位候选人。如果不是，我们从所有选票中删除垫底的候选人，并重新运行具有剩余候选人的函数。

此版本是递归的，因为这会导致更清晰的代码。但请注意，递归深度不太可能成为问题，除非您有数千名候选人参加比赛，因为每个递归步骤都会减少候选人的数量。

演练

第一轮我们有这些选票：

ACBED, BDAFG, CBD, BDEAH, ABGHF, GEBHD, ECDBG, AB, DG, FEC, FCGAE, BCGAE, ABFG

这些 first-place 票数：

{A: 4, B: 3, C: 1, D: 1, E: 1, F: 2, G: 1, H: 0}

我们还没有获得多数票。由于 H 的计数最低，我们将其从每张选票中删除：


ACBED, BDAFG, CBD, BDEA<b>H</b>, ABG<b>H</b>F, GEB<b>H</b>D, ECDBG, AB, DG, FEC, FCGAE, BCGAE, ABFG
ACBED, BDAFG, CBD, BDEA,  ABGF,  GEBD,  ECDBG, AB, DG, FEC, FCGAE, BCGAE, ABFG

有了这些 first-place 票数：

{A: 4, B: 3, C: 1, D: 1, E: 1, F: 2, G: 1}

我们随机选择 first-place 计数最低的一个 C 并将其删除：

ABED, BDAFG, BD, BDEA, ABGF, GEBD, EDBG, AB, DG, FE, FGAE, BGAE, ABFG

{A: 4, B: 4, D: 1, E: 1, F: 2, G: 1}

然后我们删除E:

ABD, BDAFG, BD, BDA, ABGF, GBD, DBG, AB, DG, F, FGA, BGA, ABFG

{A: 4, B: 4, D: 2, F: 2, G: 1}

然后 G:

ABD, BDAF, BD, BDA, ABF, BD, DB, AB, D, F, FA, BA, ABF

{A: 4, B: 5, D: 2, F: 2}

和D：

AB, BAF, B, BA, ABF, B, B, AB, F, FA, BA, ABF

{A: 4, B: 6, F: 2}

然后F:

AB, BA, B, BA, AB, B, B, AB, A, BA, AB

{A: 5, B: 6}

我们终于占了多数，return B.

在 JavaScript 中进行即时决选投票并增加选票

Instant-Runoff Voting in JavaScript with Additional Votes

javascript

voting

voting-system

演练