Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitaed14c4

Browse files
authored
Merge pull requestalgorithm-visualizer#222 from kopiro/PR-STABLEMATCHING
Stable matching algorithm
2 parents6b5f1a8 +6cdd9d5 commitaed14c4

File tree

4 files changed

+99
-1
lines changed

4 files changed

+99
-1
lines changed

‎algorithm/category.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -114,7 +114,8 @@
114114
"flood_fill":"Flood Fill",
115115
"cellular_automata":"Cellular Automata",
116116
"create_maze":"Create Maze",
117-
"magic_square":"Magic Square"
117+
"magic_square":"Magic Square",
118+
"stable_matching":"Stable Matching"
118119
},
119120
"name":"Uncategorized"
120121
}
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
functioninit(rank){
2+
varo={};
3+
for(varkinrank){
4+
o[k]={
5+
key:k,
6+
stable:false,
7+
rank_keys:rank[k]
8+
};
9+
}
10+
returno;
11+
}
12+
13+
functionextractUnstable(Q){
14+
for(varkinQ){
15+
if(Q[k].stable===false){
16+
returnQ[k];
17+
}
18+
}
19+
}
20+
21+
varA=init(ARank),B=init(BRank);
22+
vara,b;
23+
24+
while((a=extractUnstable(A))!=null){
25+
26+
logTracer._print('Selecting '+a.key)._wait();
27+
28+
varbKey=a.rank_keys.shift();
29+
varb=B[bKey];
30+
31+
logTracer._print('--> Choicing '+b.key)._wait();
32+
33+
if(b.stable===false){
34+
35+
logTracer._print('--> '+b.key+' is not stable, stabilizing with '+a.key)._wait();
36+
37+
a.stable=b;
38+
b.stable=a;
39+
40+
tracerA._select(_aKeys.indexOf(a.key))._wait();
41+
tracerB._select(_bKeys.indexOf(b.key))._wait();
42+
43+
}else{
44+
45+
varrank_a_in_b=b.rank_keys.indexOf(a.key);
46+
varrank_prev_a_in_b=b.rank_keys.indexOf(b.stable.key);
47+
if(rank_a_in_b<rank_prev_a_in_b){
48+
49+
logTracer._print('--> '+bKey+' is more stable with '+a.key+' rather than '+b.stable.key+' - stabilizing again')._wait();
50+
51+
A[b.stable.key].stable=false;
52+
tracerA._deselect(_aKeys.indexOf(b.stable.key))._wait();
53+
54+
a.stable=b;
55+
b.stable=a;
56+
57+
tracerA._select(_aKeys.indexOf(a.key))._wait();
58+
tracerB._select(_bKeys.indexOf(b.key))._wait();
59+
}
60+
61+
}
62+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
varARank={
2+
'Flavio' :['Valentine','July','Summer','Violet'],
3+
'Stephen':['Summer','July','Valentine','Violet'],
4+
'Albert' :['July','Violet','Valentine','Summer'],
5+
'Jack' :['July','Violet','Valentine','Summer']
6+
};
7+
8+
varBRank={
9+
'July':['Jack','Stephen','Albert','Flavio'],
10+
'Valentine':['Flavio','Jack','Stephen','Albert'],
11+
'Violet':['Jack','Stephen','Flavio','Albert'],
12+
'Summer':['Stephen','Flavio','Albert','Jack'],
13+
};
14+
15+
vartracerA=newArray1DTracer('A');
16+
vartracerB=newArray1DTracer('B');
17+
18+
var_aKeys=Object.keys(ARank);
19+
var_bKeys=Object.keys(BRank);
20+
tracerA._setData(_aKeys);
21+
tracerB._setData(_bKeys);
22+
23+
varlogTracer=newLogTracer('Console');
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
{
2+
"Stable Matching":"In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is not stable if: There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and also prefers A over the element to which B is already matched. In other words, a matching is stable when there does not exist any match (A, B) by which both A and B would be individually better off than they are with the element to which they are currently matched.",
3+
"Complexity": {
4+
"time":" $O(N^2)$"
5+
},
6+
"References": [
7+
"<a href='https://en.wikipedia.org/wiki/Stable_marriage_problem'>Wikipedia</a>"
8+
],
9+
"files": {
10+
"basic":"Stable Matching"
11+
}
12+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp