/
subsetChooser.go
93 lines (86 loc) · 2.2 KB
/
subsetChooser.go
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
/*
* Copyright 2011 Colin Patrick McCabe
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 2.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package main
import (
"fmt"
)
/*
* A subsetChooser can be used to step through all the possible subarrays of an
* array.
* So if our starting array was [ "a", "b", "c" ], and subset size was 2, we'd
* step through [ "a", "b" ], [ "a", "c" ], and [ "b", "c" ]. Etc.
*/
type SubsetChooser struct {
maxIdx uint
subsetSize uint
comb int64
}
// Creates a new SubsetChooser
func NewSubsetChooser(maxIdx uint, subsetSize uint) *SubsetChooser {
ch := &SubsetChooser {maxIdx, subsetSize, 0}
if (subsetSize > 63) {
panic("sorry, this class can't handle subset sizes greater than 63" +
"due to its use of 64-bit numbers to represent subsets.")
}
ch.comb = pow64(2, uint(subsetSize)) - 1
return ch
}
// Gets the current subset
func (ch *SubsetChooser) Cur() []uint {
var i uint
ret := make([]uint, ch.subsetSize)
var j uint = 0
for i = 0; i < ch.maxIdx; i++ {
if (((1 << i) & ch.comb) != 0) {
ret[j] = i
j++
}
}
if (j != ch.subsetSize) {
panic(fmt.Sprintf("logic error: failed to return a subset of size %d",
ch.subsetSize))
}
return ret
}
// Advance to the next subset.
// Based on HAKMEM item 175.
// Returns false if there are no more subsets to view, true otherwise
func (ch *SubsetChooser) Next() bool {
if (ch.comb == 0) {
return false
}
u := ch.comb & -ch.comb
v := u + ch.comb
if (v==0) {
ch.comb = 0
return false
}
ch.comb = v + (((v^ch.comb)/u)>>2);
if (ch.comb >= (1<<ch.maxIdx)) {
ch.comb = 0
return false
}
return true
}
func pow64(a int64, b uint) int64 {
var ret int64
ret = 1
var i uint
for i = 0; i < b; i++ {
ret = ret * a
}
return ret
}