-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trees.ts
107 lines (98 loc) · 4.3 KB
/
Trees.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
export class Trees {
/***
* BranchAndBound based on https://en.wikipedia.org/wiki/Branch_and_bound, this function
* is used to find the optimal answer to a combinatorial problem.
* @param nCombinations number from 0 to nCombinations
* @param objective_function function that evaluates combination, against some optimisation and responds with true if search should continue and false if this combination branch should terminate.
* @returns all remaining / possible combinations
*
* This function is literal, it creates a bag filled with elements, it then removes item from the bag,
* removed element is then used to form a pattern. It keeps doing this for all possible combinations of a bag state.
*/
public static BranchAndBound(nCombinations:number, objective_function:(combination : Array<number>) => boolean) : Array<Array<number>> {
//create a bag full of numbers from 0 to nCombinations
const bagOrigin:Array<number> = [...Array(nCombinations).keys()];
//create tree with first element being the full bag and the second element being empty pattern
const tree = [[[...bagOrigin], []]];
const combinations = [];
let branch = null;
while(branch = tree.shift()) {
//go through the entire bag, at each instance take 1 item out and from that create a new pattern
//by appending this new item that was taken out to the pattern element
for(let i:number = 0; i < branch[0].length; i++) {
const bagReduced = [...branch[0]];
const combinationNew = [...branch[1]];
const omittedElement = bagReduced.splice(i, 1)[0];
combinationNew.push(omittedElement);
//see if there is optimisation function present, if it is, see if
//search needs to continue or this particular combination tree should terminate
if(objective_function && !objective_function(combinationNew)) {
continue;
}
tree.push([bagReduced, combinationNew]);
combinations.push(combinationNew);
}
}
return combinations;
}
/***
* BranchCounter counts discrete element occurrences within the array. For example given
* [0, 2] and [0, 1] ordered elements calling DiscreteCounter([0, 2], tree, 3) and DiscreteCounter([0, 1], tree, 3)
* would create the following tree
* [
* [
* [
* [],
* [
* [[],[],[]],
* [1]
* ],
* [
* [[],[],[]],
* [1]
* ],
* ],
* [2]
* ],
* [],
* []
* ]
* @param oredered ordered array with discrete unique numbers such as [0,1,2,3,4] or [1,2,3,0]
* @param branch prefilled initialized array
*/
public static BranchCounter(ordered: Array<number>, branch: any[], base: number, level: number = 0) : void {
if(level >= ordered.length) {
return;
}
//current level in the array, get the value
//value becomes the index
const index = ordered[level];
//if current branch already initialised this index increment,
//if not initialise at 1 with new sub array
if(branch[index]) {
branch[index][1]++;
} else {
branch[index] = [new Array(base), 1];
}
//recurse through the array creating new branches
Trees.BranchCounter(ordered, branch[index][0], base, level+1);
}
public static BranchCounterMax(tree: any[], base: number) : Array<number> {
let branch = tree, maxPattern = Array<number>();
while(true) {
let max = 0, maxIndex = null;
for(let i=0; i < base; i++) {
if(branch[i] && max < branch[i][1] && 3 <= branch[i][1]) {
max = branch[i][1];
maxIndex = i;
}
}
if(maxIndex == null || branch[maxIndex] == null) {
break;
}
maxPattern.push(maxIndex);
branch = branch[maxIndex][0];
}
return maxPattern;
}
}