选举中的算法选票 [英] Algorithm Ballots cast in an Election

问题描述

有人可以帮我解决这个问题吗?

Can someone help me solve this?

我们最近举行了3个职位的选举.

We recently held an election for 3 positions.

有6名候选人.

每个成员可以投3票，但不能多次投票给同一个人.

Each member could cast 3 votes but could not vote for the same person more than once.

投了134张选票.(总票数402)

134 ballots were cast. (402 total votes)

最后的统计是

result = {a:91, b:66, c:63, d:63, e:60, f:59}

我可以轻松确定20种可能的唯一投票

I can easily determine the 20 possible unique ballots cast

result.keys.combination(3).to_a

但是很明显，考虑到可能的组合数量，蛮力将非常耗时，因此我希望有人能够提供一种实用的算法来解决这个问题.

But obviously given the number of possible combinations brute force would be impossibly time consuming so I am hoping someone can provide an algorithm to solve this practically.

我正在尝试找到一种合理有效的方法来确定单个可能的选票总数，但是如果您可以提供多个或所有可能的选票，那就太好了.

I am trying to find a reasonably efficient way to determine a single possible tally of ballots but if you can provide multiple or all possible tallies that would be amazing.

推荐答案

如果任何人的投票数超过三分之一，或者投票数不是三的倍数，则没有可能的答案.

If anybody has more than one third of the possible votes, or if the number of votes is not a multiple of three, there is no possible answer.

如果至少还剩下三票，而且没有人拥有超过三分之一的可能票数，请决定一张选票，让前三名候选人各投一票，并将总数减一.

If there are at least three votes left, and nobody has more than one third of the possible votes, decide on a ballot paper that gives the top three candidates one vote each and reduce their totals by one.

此过程将停止，即占所有选票或拥有超过三分之一的选票.我认为，最糟糕的情况是，您进入(N，N-1，N-1，N)的票数(N + 1，N，N，N)，而该点数没有减少，但得不到一点第三，所以我认为您可以继续进行此过程以说明所有投票.

This process stops either with all votes accounted for or with somebody having more than one third of the vote. I think the worst case for this is votes (N+1, N, N, N) where you go to (N, N-1, N-1, N) where the count not decremented gains a little but does not reach one third, so I think you can continue this process to account for all votes cast.

显然有许多不同的等效计数.在两个候选者中不重叠的任何一对动作都有至少一个可能的替代解释.产生多种解决方案的一种方法是，仅在没有任何款项能获得剩余的三分之一以上投票的约束的情况下，随机选择可能的选票.另一个办法是随机重新排列答案，并遵循 https://en.wikipedia.org/wiki/Metropolis％E2％80％93Hastings_algorithm (尽管我还没有证明任何特定的小型重排都会使可能的解决方案集联系起来)

There are obvious many different equivalent counts. Any pair of actions that do not overlap in two candidates has at least one possible alternative interpretation. One way to generate multiple solutions would be to chose possible ballots at random subject only to the constraint that no sum ever gets to more than one third of the possible votes left. Another would be to rearrange answers at random and follow https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm (although I have not proved that any particular set of small rearrangements makes the set of possible solutions connected)

这篇关于选举中的算法选票的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！