RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/db/d80/gale__shapley_8cpp_source.html below:

TheAlgorithms/C++: greedy_algorithms/gale_shapley.cpp Source File

Go to the documentation of this file. 47 const

std::vector<std::vector<std::uint32_t>>& secondary_preferences,

48 const

std::vector<std::vector<std::uint32_t>>& primary_preferences) {

49

std::uint32_t num_elements = secondary_preferences.size();

50

std::vector<std::uint32_t> matches(num_elements, -1);

51

std::vector<bool> is_free_primary(num_elements,

true

);

52

std::vector<std::uint32_t> proposal_index(

57 int

free_primary_index = -1;

60 for

(std::uint32_t i = 0; i < num_elements; i++) {

61 if

(is_free_primary[i]) {

62

free_primary_index = i;

68 if

(free_primary_index == -1)

72

std::uint32_t secondary_to_propose =

73

primary_preferences[free_primary_index]

74

[proposal_index[free_primary_index]];

75

proposal_index[free_primary_index]++;

78

std::uint32_t current_match = matches[secondary_to_propose];

81 if

(current_match == -1) {

82

matches[secondary_to_propose] = free_primary_index;

83

is_free_primary[free_primary_index] =

false

;

86 auto

new_proposer_rank =

87

std::find(secondary_preferences[secondary_to_propose].begin(),

88

secondary_preferences[secondary_to_propose].end(),

90 auto

current_match_rank =

91

std::find(secondary_preferences[secondary_to_propose].begin(),

92

secondary_preferences[secondary_to_propose].end(),

96 if

(new_proposer_rank < current_match_rank) {

97

matches[secondary_to_propose] = free_primary_index;

98

is_free_primary[free_primary_index] =

false

;

99

is_free_primary[current_match] =

116

std::vector<std::vector<std::uint32_t>> primary_preferences = {

117

{0, 1, 2, 3}, {2, 1, 3, 0}, {1, 2, 0, 3}, {3, 0, 1, 2}};

118

std::vector<std::vector<std::uint32_t>> secondary_preferences = {

119

{1, 0, 2, 3}, {3, 0, 1, 2}, {0, 2, 1, 3}, {1, 2, 0, 3}};

121

secondary_preferences, primary_preferences) ==

122

std::vector<std::uint32_t>({0, 2, 1, 3}));

125

primary_preferences = {

126

{0, 2, 1, 3}, {2, 3, 0, 1}, {3, 1, 2, 0}, {2, 1, 0, 3}};

127

secondary_preferences = {

128

{1, 0, 2, 3}, {3, 0, 1, 2}, {0, 2, 1, 3}, {1, 2, 0, 3}};

130

secondary_preferences, primary_preferences) ==

131

std::vector<std::uint32_t>({0, 3, 1, 2}));

134

primary_preferences = {{0, 1, 2}, {2, 1, 0}, {1, 2, 0}};

135

secondary_preferences = {{1, 0, 2}, {2, 0, 1}, {0, 2, 1}};

137

secondary_preferences, primary_preferences) ==

138

std::vector<std::uint32_t>({0, 2, 1}));

141

primary_preferences = {};

142

secondary_preferences = {};

144

secondary_preferences, primary_preferences) ==

145

std::vector<std::uint32_t>({}));

static void tests()

Self-test implementations.

int main()

Main function.

Functions for the Gale-Shapley Algorithm.

std::vector< std::uint32_t > gale_shapley(const std::vector< std::vector< std::uint32_t > > &secondary_preferences, const std::vector< std::vector< std::uint32_t > > &primary_preferences)

The main function that finds the stable matching between two sets of elements using the Gale-Shapley ...

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4