-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathorganize.js
More file actions
131 lines (110 loc) · 3.79 KB
/
organize.js
File metadata and controls
131 lines (110 loc) · 3.79 KB
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
function reduce(size_of_set) {
var organizations = [];
var organization = [];
for (var i = 0; i < size_of_set; i ++) {
organization = [size_of_set - i];
for (var j = 0; j < i; j ++) {
organization.push(1);
}
organizations.push(organization.slice(0));
}
return organizations;
}
function merge(organizations) {
var new_organizations = [];
var organization = [];
var pointer = 1;
for (var i = 0; i < organizations.length; i ++) {
new_organizations = new_organizations.concat(quickMerge(organizations[i].slice(0)));
new_organizations = new_organizations.concat(wholeMerge(organizations[i].slice(0)));
}
return unique(organizations.concat(new_organizations));
}
function quickMerge(organization) {
let pointer = 1;
let organizations = [];
// quick merge
while (mergePossible(organization, pointer)) {
organization = mergeIndex(organization, pointer);
organizations.push(organization.slice(0));
if (organization[pointer] == organization[0]) {
pointer ++;
}
}
return organizations;
}
function wholeMerge(organization) {
let pointer = 1;
let organizations = [];
// quick merge
while (globalMergePossible(organization, pointer)) {
if (mergePossible(organization, pointer)) {
organization = mergeIndex(organization, pointer);
organizations.push(organization.slice(0));
pointer ++;
} else {
pointer --;
}
}
return organizations;
}
function mergeIndex(organization, index) {
if (organization[index + 1] > 1) {
organization[index] ++;
organization[index + 1] --;
} else {
var value = organization.splice(index, 1)[0];
organization[index] += value;
}
return organization;
}
function globalMergePossible(organization, index) {
return mergePossible(organization, index) || index > 0;
}
function mergePossible(organization, index) {
return organization.length - 1 > index && organization[index - 1] > organization[index];
}
function rotate(organizations) {
var new_organizations = [];
for (var i = 0; i < organizations.length; i ++) {
new_organizations = new_organizations.concat(orientations(organizations[i]));
}
return new_organizations;
}
function orientations(organization) {
if (organization.length == 1 || organization.toString() == organization.slice(0).reverse().toString()) {
return [organization];
} else if (organization.length == 2) {
return [organization, [organization[1], organization[0]]]
} else {
let orientation_slices = orientations(organization.slice(1));
let all_orientations = [];
let temp_orientation = [];
for (let i in orientation_slices) {
compare_orientation = [organization[0]].concat(orientation_slices[i]);
temp_orientation = compare_orientation.slice(0);
do {
temp_orientation.push(temp_orientation.shift());
if (uniqueOrganization(temp_orientation, all_orientations)) {
all_orientations.push(temp_orientation.slice(0));
}
} while (temp_orientation.toString() !== compare_orientation.toString())
}
return all_orientations;
}
}
function uniqueOrganization(organization, organizations) {
for (let i in organizations) {
if (organizations[i].toString() == organization.toString()) {
return false;
}
}
return true;
}
function unique(organizations) {
let set = new Set(organizations.map(JSON.stringify));
return Array.from(set).map(JSON.parse);
}
exports.generate = function(size_of_set) {
return unique(rotate(merge(reduce(size_of_set))));
}