c++ - 排名选择投票
问题描述
我目前正在编写一个程序，它根据包含 3 次测试选举的输入文本文件执行一系列排名选择选举，每个测试选举中有 3 名候选人中的 5 票选民选择。然后它输出每次选举的获胜候选人。
问题是对于第一次测试选举，获胜者的输出显示为“Candidate #-1 wins”。假设是“候选人#2 获胜”。根据第一次测试选举的结果。
我尝试在 int main() 之前将返回值从“-1”更改为“2”。它确实输出了我想要的东西，但我试图避免硬编码。如果有人能给我提示如何以其他方式解决此问题，我将不胜感激！
文本文件（elections.txt）：
15
1
2
3
3
2
1
2
1
3
1
2
3
2
3
1
15
1
2
3
1
2
3
1
2
3
1
2
3
2
1
3
15
3
2
1
3
2
1
3
1
2
1
2
3
1
3
2
我的代码：
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
using namespace std;
const char *FILENAME = "elections.txt";
const int MAXBALLOTS = 500;
const int NUM_CANDIDATES = 3;
int elect_candidate(int ballots[MAXBALLOTS][NUM_CANDIDATES],
int numBallots) {
int tally[NUM_CANDIDATES + 1] = { 0 };
double percentages[NUM_CANDIDATES + 1];
for (int i = 0; i < numBallots; i++) {
int j;
for (j = 0; j < NUM_CANDIDATES; ++j) {
if (ballots[i][j] > 0)
break;
}
if (j < NUM_CANDIDATES) {
int choice = ballots[i][j];
tally[choice]++;
}
}
int best = 1;
int bestCount = 0;
int worst = 1;
cout << "Percentages for each candidate: " << endl;
for (int i = 1; i < NUM_CANDIDATES + 1; i++) {
percentages[i] = (double)tally[i] / numBallots;
cout << fixed << setprecision(2);
cout << "#" << i << ": " << percentages[i];
cout << endl;
if (tally[i] > tally[best]) {
best = i;
bestCount = 1;
} else if (tally[i] == tally[best]) {
++bestCount;
} else if (tally[i] < tally[worst]) {
worst = i;
}
}
if (best == worst) {
return 0;
}
if (2 * tally[best] > numBallots) {
return best;
} else {
for (int i = 0; i < numBallots; i++) {
for (int j = 0; j < NUM_CANDIDATES; ++j) {
if (tally[ballots[i][j]] == tally[worst]) {
ballots[i][j] = 0;
}
}
}
}
return -1;
}
int main()
{
ifstream f(FILENAME);
string tmp;
int nLines;
int numBallots = 0;
int ballots[MAXBALLOTS][NUM_CANDIDATES];
cout << "********************" << endl;
cout << "C++ Election of 2020" << endl;
cout << "********************" << endl;
// While we are not at end-of-file
while (getline(f, tmp)) {
// Read the number of lines for this election
nLines = atoi(tmp.c_str());
// Read in each ballot
for (int i = 0; i < nLines; i += 3) {
// Read in a single ballot (3 lines each)
cout << "Read ballot: ";
for (int j = 0; j < NUM_CANDIDATES; j++) {
getline(f, tmp);
ballots[numBallots][j] = atoi(tmp.c_str());
cout << " " << ballots[numBallots][j];
}
numBallots++;
cout << endl;
}
cout << "Read " << numBallots << " ballots..." << endl;
cout << endl;
int winner = -1;
// Run the election
winner = elect_candidate(ballots, numBallots);
cout << "********************" << endl;
cout << "Candidate #" << winner << " wins." << endl;
cout << "********************" << endl;
cout << endl;
numBallots = 0;
}
return 0;
}
我的输出：
********************
C++ Election of 2020
********************
Read ballot: 1 2 3
Read ballot: 3 2 1
Read ballot: 2 1 3
Read ballot: 1 2 3
Read ballot: 2 3 1
Read 5 ballots...
Percentages for each candidate:
#1: 0.40
#2: 0.40
#3: 0.20
********************
Candidate #-1 wins.
********************
Read ballot: 1 2 3
Read ballot: 1 2 3
Read ballot: 1 2 3
Read ballot: 1 2 3
Read ballot: 2 1 3
Read 5 ballots...
Percentages for each candidate:
#1: 0.80
#2: 0.20
#3: 0.00
********************
Candidate #1 wins.
********************
Read ballot: 3 2 1
Read ballot: 3 2 1
Read ballot: 3 1 2
Read ballot: 1 2 3
Read ballot: 1 3 2
Read 5 ballots...
Percentages for each candidate:
#1: 0.40
#2: 0.00
#3: 0.60
********************
Candidate #3 wins.
********************
预期输出：
********************
C++ Election of 2020
********************
Read ballot: 1 2 3
Read ballot: 3 2 1
Read ballot: 2 1 3
Read ballot: 1 2 3
Read ballot: 2 3 1
Read 5 ballots...
Percentages for each candidate:
#1: 0.40
#2: 0.40
#3: 0.20
********************
Candidate #2 wins.
********************
Read ballot: 1 2 3
Read ballot: 1 2 3
Read ballot: 1 2 3
Read ballot: 1 2 3
Read ballot: 2 1 3
Read 5 ballots...
Percentages for each candidate:
#1: 0.80
#2: 0.20
#3: 0.00
********************
Candidate #1 wins.
********************
Read ballot: 3 2 1
Read ballot: 3 2 1
Read ballot: 3 1 2
Read ballot: 1 2 3
Read ballot: 1 3 2
Read 5 ballots...
Percentages for each candidate:
#1: 0.40
#2: 0.00
#3: 0.60
********************
Candidate #3 wins.
********************
解决方案
这看起来像是一个你想自己解决的学习练习，而我的政策是不为这些练习编写代码。
但是，如果我可以提出一个建议：尝试将每张选票表示std::vector为候选人，按优先顺序递增存储，即最后一个选择，倒数第二个，...，第二选择，第一选择。然后将选票存储在std::multimap其键是每个选票当前已选择的候选人中。（编辑： Astd::unordered_multimap更好。）您可以插入拥有选票数据的智能指针，或者只是移动向量并为自己节省额外的间接级别。例如：
using Candidate = int;
// A ranking of candidates in order of last-place to first-place:
using Ballot = std::vector<Candidate>;
// A collection of ballots, each keyed to the highest-ranking candidates
// on the ballot who is still alive:
using BallotBox = std::unordered_multimap< Candidate, Ballot >;
因此，如果我更喜欢 Alice 而不是 Bob 和 Bob 而不是 Carol，我的选票将存储在 中BallotBox，其中BallotNode的键是Candidate alice，我的第一选择，并且引用选票数据{carol, bob, alice}。如果 Alice 被淘汰，算法会减少Ballot向量的长度，使其现在变为{carol, bob}，并将BallotNode密钥更新为bob，我的新选择。
您可以使用 将每张选票插入BallotBox（多地图容器）中ballot_box.emplace(BallotNode( candidate, ballot ))。然后，您将每张选票插入到BallotBox您的输入循环中，并将其本身的所有权传递BallotBox给计算选票的函数，以供使用。
计算候选人的票数是成员函数ballot_box.count(that_jerk)。代表给定候选人选票的节点是范围内的节点ballot_box.equal_range(loser)。
每个Ballot都是一个向量，其最喜欢的选择稍后存储。因此，找到它的下一个选择只是减少向量的长度。这是一个微不足道的恒定时间操作。如果您反向迭代直到找到仍在竞选中的候选人，您将保持任何选票的最后一个元素是其当前最喜欢的选择的不变性。
然后，您可以通过迭代为每个被淘汰的候选人重新分配所有选票，提取与键匹配的每个选票BallotNode，找到Ballot其中包含的较小的邪恶，创建一个其键是选票上的下一个候选人的新节点，然后插入或放置新节点回到多图。
您必须创建一个新节点才能插入，并且不能安全地重新使用您提取的节点，因为您需要更新其密钥，该密钥是恒定的。但是，您可以移动而不是复制其选票数据。
你没有解释排名选择算法的细节，特别是是否有决胜局。例如，如果第一个 tiebreaker 是第一名的票数，第二个 tiebreaker 是第二名的票数，依此类推，您需要在开始修改数据之前制作 tiebreaker 数据的副本在你的投票箱里。
最后，由于可能出现平局，请考虑定义一个可以返回一个或多个获胜者的 Result 类型，例如 a std::set<Candidate>。
好的，一些代码
我等了几天，我改变了足够的输入格式，你不能把它转过来。但这是一个足够有趣的问题，我自己解决了一个非常相似的问题，并学到了一些东西。我遇到的最棘手的错误是从投票箱中提取节点会使其中的迭代器无效，因此我必须更改为失败的候选人拉票的方式。
然后我返回并更改了数据结构std::multimap和std::set（用于使用树）std::unordered_multimap和std::unordered_set（用于使用哈希表）。这不仅可以加快访问速度，而且如果您事先知道输入大小，您可以使用它预先进行.reserve()分配。
最终结果没有任何手动内存管理，没有任何深拷贝，没有编写任何新类，甚至没有创建任何智能指针。它只是移动 STL 容器。
// This program requires C++17 or higher.
/* For the purposes of this exercise, data is read from standard input.
* Data consists of zero or more election tallies, terminated by newlines.
* The input encoding is UTF-8. Lines beginning with # are comments, and
* ignored. Parsing and input-checking are minimal.
*
* Each election tally consists of:
* - One line consisting of the number of ballots, N
* - N ballots, each on its own line, consisting of space-separated integers,
* each identifying a candidate. Higher-ranked candidates appear before
* lower-ranked ones on each ballot, no candidate may appear more than
* once on the same ballot, and a candidate must be the first choice of at
* least one voter to win.
*
* The expected output is, for each election tally:
* The ID of the inning candidates (or a space-separated list of all candid=
* ates tied for first place) followed by a newline.
*
* If more than one candidate is tied for last place, which last-place can-
* didate is eliminated is arbitrary. This could lead to an ambifuous result.
* The algorithm doesn’t do tiebreakers (such as most first-place votes).
*/
#include <algorithm>
#include <array>
#include <assert.h>
#include <iostream>
#include <limits>
#include <memory>
#include <stdexcept>
#include <stdlib.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using Candidate = int;
// A ranking of candidates in order of last-place to first-place:
using Ballot = std::vector<Candidate>;
// A collection of ballots, each keyed to the highest-ranking candidates
// on the ballot who is still alive:
using BallotBox = std::unordered_multimap< Candidate, Ballot >;
using CandidateSet = std::unordered_set<Candidate>;
// Magic constant to make turn off lenght-checking:
constexpr auto huge_size = std::numeric_limits<std::streamsize>::max();
template <class It>
std::ostream& print_list( std::ostream& out,
const It& begin,
const It& end )
/* Prints the elements in range to the provided stream, separated by spaces.
* The type It must be a forward iterator. Utility function intended to be
* called by operator<< overloads.
*/
{
if (begin != end) {
out << *begin;
It it = begin;
++it;
while ( it != end )
out << ' ' << *it++;
}
return out;
}
inline std::ostream& operator<<( std::ostream& out, const CandidateSet& x )
{
return print_list( out, x.cbegin(), x.cend() );
}
inline std::ostream& operator<<( std::ostream& out, const Ballot& x )
{
return print_list( out, x.cbegin(), x.cend() );
}
CandidateSet get_unique_keys( const BallotBox& x ) noexcept
/* Generates the set of keys in x.
*/
{
CandidateSet results;
if (!x.empty()) {
auto it = x.cbegin();
const Candidate* previous = &it->first;
results.emplace(*previous);
++it;
while (it != x.cend()) {
if (it->first != *previous) {
previous = &it->first;
results.emplace(*previous);
}
++it;
} // end while
} // end if
return results; // Guaranteed copy elision.
}
BallotBox collect_ballots( std::istream& in = cin )
/* Creates the first round of the next election in the input stream, or
* else throws a std::runtime_error.
*/
{
unsigned n_votes;
in >> n_votes;
if (!in)
throw std::runtime_error("Expected: number of votes.");
if ( in.peek() == '\n' )
in.get();
else
throw std::runtime_error("Expected: newline.");
BallotBox ballot_box;
ballot_box.reserve(n_votes);
while (n_votes--) {
while( in.peek() == '#' )
in.ignore( huge_size, '\n');
Ballot ballot;
do {
Candidate c;
in >> c;
if (!in)
throw std::runtime_error("Expected: Candidate ID.");
ballot.push_back(c);
} while ( in.get() == ' ' );
// The above never checks which non-space character it consumed, but it
// should have been a newline.
// For convenience, we inserted elements in the reverse order that our
// algorithm needs. Reversing is faster than front-insertions.
std::reverse( ballot.begin(), ballot.end() );
// Now we need to insert a node keyed to the first choice into the
// BallotBox (multimap).
const Candidate kodos = ballot.back();
ballot_box.emplace( kodos, std::move(ballot) );
}
while (in && !in.eof() && in.peek() == '\n')
in.get(); // Chomp trailing newlines.
return ballot_box; // Guaranteed copy elision.
}
CandidateSet count_ballots( BallotBox&& ballot_box )
/* Consumes the initial state of the election and returns the Results of the
* election.
*/
{
using Tally = BallotBox::size_type;
constexpr Tally votes_for_Stalin =
std::numeric_limits<Tally>::max();
constexpr Candidate noman = -1;
CandidateSet candidates = get_unique_keys(ballot_box);
Tally most_votes = 0;
Tally fewest_votes = votes_for_Stalin;
Candidate loser = noman;
Candidate winner = noman;
for ( const Candidate i : candidates ) {
const Tally votes = ballot_box.count(i);
if (votes > most_votes) {
most_votes = votes;
winner = i;
}
if (votes < fewest_votes) {
fewest_votes = votes;
loser = i;
}
} // end for
while ( most_votes < (ballot_box.size()/2U + 1U) &&
most_votes > fewest_votes &&
!candidates.empty() &&
!ballot_box.empty() ) {
std::vector<Ballot> changed_votes;
changed_votes.reserve(fewest_votes);
candidates.erase(loser);
while ( auto handle = ballot_box.extract(loser) ) {
Ballot& ballot = handle.mapped();
do {
ballot.pop_back();
} while ( candidates.find(ballot.back()) == candidates.end() );
if (!ballot.empty()) {
changed_votes.emplace_back(std::move(ballot));
}
} // end while
for ( Ballot& b : changed_votes ) {
assert(!b.empty());
const Candidate new_key = b.back();
ballot_box.emplace( std::move(new_key), std::move(b) );
}
most_votes = 0;
fewest_votes = votes_for_Stalin;
loser = noman;
winner = noman;
for ( const Candidate i : candidates ) {
const auto votes = ballot_box.count(i);
if (votes > most_votes) {
most_votes = votes;
winner = i;
}
if (votes < fewest_votes) {
fewest_votes = votes;
loser = i;
} // end if
} // end for
} // end while
if ( most_votes > fewest_votes ) {
/* If this branch is reached, the while loop did not fail because all the
* remaining candidates were tied: one candidate got more votes than
* another. Nor did it terminate because either the set of remaining can-
* didates or the container of votes were empty. Therefore, the loop
* terminated for the only other possible reason: one candidate has won
* a majority.
*/
candidates.clear();
candidates.insert(winner);
}
return candidates; // Guaranteed copy elision.
}
int main()
{
try {
while( cin && !cin.eof() ) {
const auto next = cin.peek();
if ( next == '#' || next == '\n' )
cin.ignore( huge_size, '\n');
else {
cout << count_ballots(collect_ballots()) << endl;
} // end if
} // end while
if (cin.fail())
throw std::runtime_error("Failed to read from standard input.");
} catch (const std::runtime_error& e) {
cout.flush();
cerr << "Error: " << e.what() << '\n';
exit(EXIT_FAILURE);
}
return EXIT_SUCCESS;
}
一些测试用例。（末尾的换行符不是可选的。）
# Test data for rankedchoice.cpp
# Expected output: 4
8
1 4 3 2
2 4 3 1
2 1 4 3
3 1 2 4
3 2 1 4
3 1 4 2
4 2 3 1
4 1 3 4
# Expected output: 4
8
4 1 3 4
4 2 3 1
3 2 1 4
3 1 2 4
2 4 3 1
2 1 4 3
1 4 3 2
3 1 4 2
# Expected output: 1
1
1 2
# Expected output: 1
1
1
# Expected output: 2
3
1 2
2 1
2
# Expected output: 1 2
2
1 2
2 1
# Expected output: 1 3
6
1 2
1 3
1
3 2
3 1
2 3
# Expected output: 1
# Because there are no first-place votes for 4, it should be eliminated,
# and the 3 4 1 2 ballots should put 1 over the top on the second ballot.
9
1 2 3 4
1 2 3 4
1 2 3 4
2 1 3 4
2 4 1 3
2 4 1 4
2 4 1 3
3 4 1 2
3 4 1 2
# Expected Output: 3
5
1 2 3
2 1 3
3 1 2
3 2 1
3
# Expected Output: 3
5
1 2 3
1 3 2
2 3 1
3 1 2
3 2 1
推荐阅读
- ag-grid - Ag-grid 数字过滤器小数分隔符
- liferay - 登录 Liferay 时出现 UserEmailAddressException
- r - 将下方单元格中的值添加到上方单元格中
- macos - OSX 的 docker 桌面上的 CouchDB 无法启动
- html - 漏洞：启用自动完成的密码类型输入
- c++ - std::strings 的 std::initializer_list 的奇怪行为
- javascript - 绑定作用域javascript
- ruby-on-rails - Rails 6 YAML 装置中的模块方法
- java - 如果通过 onBackPressed() 从 MainActivity 运行 ScrollTo() 将无法正常工作
- c# - 使用具有只读属性和内部 ctor 的返回类型模拟第三方接口