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

Commitd6bbf8a

Browse files
committed
Merge remote-tracking branch 'upstream/master' into pr-freivalds
# Conflicts:#algorithm/category.json
2 parentsfe8bc41 +263fef6 commitd6bbf8a

File tree

11 files changed

+282
-5
lines changed

11 files changed

+282
-5
lines changed

‎algorithm/category.json‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -63,7 +63,8 @@
6363
"list": {
6464
"euclidean_algorithm":"Euclidean Algorithm",
6565
"sieve_of_eratosthenes":"Sieve of Eratosthenes",
66-
"freivalds_algorithm":"Freivalds Algorithm"
66+
"freivalds_algorithm":"Freivalds Algorithm",
67+
"miller_rabin_primality_test":"Miller-Rabin primality test"
6768
},
6869
"name":"Number Theory"
6970
},
@@ -115,7 +116,8 @@
115116
"flood_fill":"Flood Fill",
116117
"cellular_automata":"Cellular Automata",
117118
"create_maze":"Create Maze",
118-
"magic_square":"Magic Square"
119+
"magic_square":"Magic Square",
120+
"stable_matching":"Stable Matching"
119121
},
120122
"name":"Uncategorized"
121123
}
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+
}

‎algorithm/graph_search/bfs/desc.json‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,14 +10,15 @@
1010
"Construction of the failure function of the Aho-Corasick pattern matcher."
1111
],
1212
"Complexity": {
13-
"time":"worst $O(|E|)$",
13+
"time":"worst $O(|V|+|E|)$",
1414
"space":"worst $O(|V|)$"
1515
},
1616
"References": [
1717
"<a href='https://en.wikipedia.org/wiki/Breadth-first_search'>Wikipedia</a>"
1818
],
1919
"files": {
2020
"tree":"Searching a tree",
21-
"shortest_path":"Finding the shortest path"
21+
"shortest_path":"Finding the shortest path",
22+
"test_bipartiteness":"Test if graph is biparted (or 2-colorable)"
2223
}
2324
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
functionBFSCheckBipartiteness(s){
2+
varQ=[];
3+
4+
// Create a new matrix to set colors (0,1)
5+
varColors=[];
6+
for(var_i=0;_i<G.length;_i++)Colors[_i]=-1;
7+
colorsTracer._setData(Colors);
8+
9+
Colors[s]=1;
10+
colorsTracer._notify(s,1);
11+
12+
Q.push(s);// add start node to queue
13+
14+
while(Q.length>0){
15+
varnode=Q.shift();// dequeue
16+
tracer._visit(node)._wait();
17+
18+
for(vari=0;i<G[node].length;i++){
19+
if(G[node][i]){
20+
21+
if(Colors[i]===-1){
22+
23+
Colors[i]=1-Colors[node];
24+
colorsTracer._notify(i,1-Colors[node]);
25+
26+
Q.push(i);
27+
tracer._visit(i,node)._wait();
28+
29+
}elseif(Colors[i]==Colors[node]){
30+
logger._print('Graph is not biparted');
31+
returnfalse;
32+
}
33+
}
34+
}
35+
}
36+
37+
logger._print('Graph is biparted');
38+
returntrue;
39+
}
40+
41+
BFSCheckBipartiteness(0);
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
vartracer=newUndirectedGraphTracer();
2+
varlogger=newLogTracer();
3+
tracer.attach(logger);
4+
5+
varG=[
6+
[0,1,0,1,1],
7+
[1,0,1,0,0],
8+
[0,1,0,1,0],
9+
[1,0,1,0,0],// <-- replace latest 0 with 1 to make G not biparted
10+
[1,0,0,0,0],
11+
];
12+
tracer._setData(G,0);
13+
14+
varcolorsTracer=newArray1DTracer('Colors');

‎algorithm/graph_search/dfs/desc.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
"Finding biconnectivity in graphs."
1515
],
1616
"Complexity": {
17-
"time":"worst $O(|E|)$",
17+
"time":"worst $O(|V|+|E|)$",
1818
"space":"worst $O(|V|)$"
1919
},
2020
"References": [
Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
// Utility function to do modular exponentiation.
2+
// It returns (x^y) % p
3+
functionpower(x,y,p)
4+
{
5+
varres=1;
6+
x=x%p;
7+
while(y>0){
8+
// If y is odd, multiply x with result
9+
if(y&1)res=(res*x)%p;
10+
// y must be even now
11+
y=y>>1;// y = y/2
12+
x=(x*x)%p;
13+
}
14+
returnres;
15+
}
16+
17+
18+
/**
19+
* Determine if N is prime using Miller-Rabin probabilistic algorithm
20+
*@param {Number} n The number
21+
*@param {Number} k An integer that determine the accuracy of the solution
22+
*@return {Boolean}
23+
*/
24+
functiontestProbablyPrime(n,k){
25+
logger._print("==> Testing number "+n);
26+
27+
if(n===1||n===3){
28+
logger._print("==> Simple case, N is 1 or 3");
29+
returntrue;
30+
}
31+
if(n%2===0){
32+
logger._print("==> Simple case, "+n+" mod 2 = 0");
33+
returnfalse;
34+
}
35+
36+
// Write (n - 1) as 2^s * d
37+
vard=n-1;
38+
while(d%2===0){
39+
d/=2;
40+
}
41+
logger._print("d = "+d);
42+
43+
// Do 5 iterations if none supplied
44+
k=k||5;
45+
varP=100*(1-(1/Math.pow(4,k)));
46+
47+
WitnessLoop:do{
48+
logger._print("Remaining iterations: #"+k);
49+
50+
vara=2+Math.floor(Math.random()*(n-4));
51+
logger._print("--> first test with random = "+a);
52+
53+
// Compute a^d % n
54+
varx=power(a,d,n);
55+
56+
if(x===1||x===n-1){
57+
logger._print("--> continue WitnessLoop, x = 1 or x = n-1");
58+
continue;
59+
}
60+
61+
logger._print("--> second test");
62+
63+
// Keep squaring x while one of the following doesn't
64+
// happen
65+
// (i) d does not reach n-1
66+
// (ii) (x^2) % n is not 1
67+
// (iii) (x^2) % n is not n-1
68+
vari=d;
69+
while(i!=n-1){
70+
x=(x*x)%n;
71+
i*=2;
72+
73+
if(x==1){
74+
logger._print("--> exiting, "+n+" is composite");
75+
returnfalse;
76+
}
77+
78+
if(x==n-1){
79+
logger._print("--> continue WitnessLoop");
80+
continue WitnessLoop;
81+
}
82+
}
83+
84+
logger._print("--> exiting, "+n+" is composite 'cause (n-1) is reached");
85+
returnfalse;
86+
87+
}while(--k);
88+
89+
logger._print("End of tests, "+n+" is probably prime with probabilty of "+P+"%");
90+
returntrue;
91+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
varlogger=newLogTracer();
2+
3+
vara=Math.floor(Math.random()*300);if(a%2===0)a+=1;
4+
testProbablyPrime(a);
5+
logger._print("----------");
6+
7+
vara=Math.floor(Math.random()*300);if(a%2===0)a+=1;
8+
testProbablyPrime(a);
9+
logger._print("----------");
10+
11+
vara=Math.floor(Math.random()*300);if(a%2===0)a+=1;
12+
testProbablyPrime(a);
13+
logger._print("----------");
14+
15+
testProbablyPrime(151);
16+
logger._print("----------");
17+
18+
testProbablyPrime(199,10);

0 commit comments

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