-
Notifications
You must be signed in to change notification settings - Fork 0
/
CombinatorialIndexer.cpp
148 lines (119 loc) · 4.3 KB
/
CombinatorialIndexer.cpp
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*
* File: CombinatorialIndexer.cpp
* Author: ph4r05
*
* Created on May 28, 2014, 11:08 AM
*/
#include "CombinatorialIndexer.h"
#include "CombinatiorialGenerator.h"
#include <string>
#include <cassert>
#include <cmath>
using namespace std;
CombinatorialIndexer::CombinatorialIndexer() : down(0), up(0), logBitInputWidth(0), binomialSums(NULL){
}
CombinatorialIndexer::~CombinatorialIndexer() {
deinit();
}
void CombinatorialIndexer::init(uint up, uint down) {
// Deinitialize first (may have been initialized before)
deinit();
this->down = down;
this->up = up;
this->logBitInputWidth = ceil(log2(up));
// Pre-compute binomial sums for combination index computation.
if (down >= 1){
binomialSums = new ULONG * [down];
for(uint order = 1; order <= down; order++){
const uint idx = order-1;
binomialSums[idx] = new ULONG[up];
binomialSums[idx][0] = 0ul;
ULONG res = 0;
for(uint i = 1; i<up; i++){
res += CombinatiorialGenerator::binomial(up-i, order-1);
binomialSums[idx][i] = res;
}
}
}
}
void CombinatorialIndexer::deinit() {
if (binomialSums!=NULL){
for(uint order = 1; order <= down; order++){
delete[] binomialSums[order-1];
binomialSums[order-1]=NULL;
}
delete[] binomialSums;
binomialSums = NULL;
}
}
inline ULONG CombinatorialIndexer::getCubeIdx(ULONG x1, ULONG x2, ULONG x3) const {
return down < 3 ? 0 : binomialSums[2][x1] + CombinatiorialGenerator::getQuadIdx(up-1-x1, x2-x1-1, x3-x1-1);
}
ULONG CombinatorialIndexer::getCombinationIdx(uint order, const ULONG* xs, uint xsOffset, ULONG Noffset, ULONG combOffset) const {
assert(order<=down);
// Small order.
if (order==0) return 0;
if (order==1) return xs[0+xsOffset] - combOffset;
if (order==2) return CombinatiorialGenerator::getQuadIdx(up-Noffset, xs[0+xsOffset]-combOffset, xs[1+xsOffset]-combOffset);
// Order 3.
// Take recursive parameters into consideration.
const ULONG x1 = xs[0+xsOffset] - combOffset;
// This is simple optimization to remove 1 recursion step.
if (order==3) {
const ULONG sum = binomialSums[2][x1+Noffset] - binomialSums[2][Noffset];
return sum + CombinatiorialGenerator::getQuadIdx(
up-1-x1-Noffset,
xs[1+xsOffset]-combOffset-x1-1,
xs[2+xsOffset]-combOffset-x1-1);
}
// Order 3 and higher.
// Sum of the previous combinations is shifted due to Noffset.
// N is reduced thus the binomial sum is shifted (originating point is smaller).
return (binomialSums[order-1][x1+Noffset] - binomialSums[order-1][Noffset]) +
getCombinationIdx(
order-1,
xs,
xsOffset+1,
Noffset+1+x1,
combOffset+1+x1
);
}
int CombinatorialIndexer::getCombinationFromIdx(uint order, ULONG* xs, ULONG idx) const {
int nOffset=0;
for(int x=order-1; x>=1; x--){
int i=up-1-nOffset;
for(; i>=0; i--){
const ULONG biSum = (binomialSums[x][i+nOffset] - binomialSums[x][nOffset]);
// If current index is bigger than the current sum, the previous sum
// helps us to determine index of the order.
if (idx >= biSum){
break;
}
}
idx-=(binomialSums[x][i+nOffset] - binomialSums[x][nOffset]);
xs[order-x-1] = i+nOffset;
nOffset = xs[order-x-1]+1;
}
// Final element is already determined.
xs[order-1] = idx + nOffset;
return 1;
}
ULONG CombinatorialIndexer::getCombinationULong(uint order, const ULONG* xs) const {
assert(order <= 0xf);
ULONG res = order & 0xf;
uint offset = 4; // order.
for(uint x=0; x<order; x++){
res |= xs[x] << offset;
offset += logBitInputWidth;
}
return res;
}
int CombinatorialIndexer::getCombinationFromULong(ULONG* xs, ULONG combUlong) const {
uint order = combUlong & 0x7;
combUlong = combUlong >> 4; // remove order.
for(uint x=0; x<order; x++){
xs[x] = combUlong & ((ULONG1 << logBitInputWidth)-1);
combUlong = combUlong >> logBitInputWidth;
}
return 1;
}