-
Notifications
You must be signed in to change notification settings - Fork 0
/
Hypercube.java
327 lines (291 loc) · 14.9 KB
/
Hypercube.java
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
import java.util.ArrayDeque;
import java.util.Scanner;
/**
* This class generates and prints hypercube corners of a given dimension using both recursive and
* iterative approaches.
*
* The main method runs some tests.
*
* @author leroy
*
*/
public class Hypercube {
/*
* DESIGN IDEA: The Hypercube class provides methods to generate and print hypercube
* corners for a given dimension 'n' using both recursive and iterative approaches.
* It utilizes a nested class called Corner to represent hypercube corners efficiently.
* Each corner is represented as a binary string of coordinates (0s and 1s).
*
* Nested Corner Class (Corner{}): The Corner class encapsulates the properties and
* behavior of a hypercube corner. It manages the coordinates of the corner and
* supports operations like flipping a coordinate or extending the dimension. A corner
* occupies O(n) memory cells, where 'n' is the dimension.
*
* Recursive Approach (recursiveWalk()): This method uses recursion to generate
* hypercube corners. Starting from the initial corner, it explores left and right
* children in each recursive call until the dimension reaches zero. When the
* dimension becomes zero, the corner is printed. This approach constructs a binary
* tree of corners. The running time is O(2^n), where 'n' is the dimension. It involves
* branching into two recursive calls at each step, resulting in a binary tree
* of depth 'n'.
*
* Iterative Approach (iterativeWalk()): This method generates and prints hypercube
* corners iteratively. It begins from dimension 1 and constructs hypercube corners
* up to dimension 'n'. The method employs a queue to manage the order of traversal and
* alternates between left and right children. Each corner is visited exactly once.
* The running time is O(n * 2^n). In the worst case, it generates and processes
* 2^n corners for each dimension (from 1 to 'n'). For each corner, it performs
* constant-time operations using a queue.
*
* Main Method (main()): The main method tests both the recursive and iterative approaches
* for dimensions 'n=3', 'n=4', and 'n=5', reporting the results.The Hypercube class
* provides efficient and clear solutions for generating and printing hypercube corners,
* offering two different approaches for comparison.
*/
/**
* This exception is thrown whenever an invalid dimension is encountered in the Hypercube class.
* An invalid dimension is one that is not a positive integer.
*
* This exception is nested for encapsulation and is protected, limiting its visibility to only
* the Hypercube class and its potential sub-classes. It is static, which means it is independent
* of any particular instance of the outer class Hypercube. Static nested classes like this
* one are used to logically group classes that are only relevant to the outer class, in this
* case, for handling dimension validation.
*
* This exception helps ensure that the Hypercube class only operates with valid dimensions,
* enhancing the robustness of the code.
*/
protected static class InvalidDimensionException extends Exception {
/**
* compiler generated serialVersionUID
*/
private static final long serialVersionUID = 1L;
/**
* Constructor with a custom message for the exception.
*
* @param dimension The invalid dimension.
*/
public InvalidDimensionException(int n) {
super("Invalid dimension " + n + ". Dimension must be a positive integer :)");
}
}
/* ********************* nested corner class ************************* */
/**
* Nested class representing a hypercube corner.
*/
public static class Corner {
int hypercube_dim; // hypercube dimension
boolean[] coordinates;
/**
* Initializes a hypercube corner for a given dimension.
*
* @param hypercube_dim The dimension of the hypercube corner.
*
* Running time is O(n), where 'n' is the dimension. This method initializes the coordinates array,
* iterating through 'n' elements to set them to false.
*/
public Corner(int hypercube_dim) {
this.coordinates = new boolean[hypercube_dim];
for (int i = 0; i < hypercube_dim; i++) this.coordinates[i] = false;
this.hypercube_dim = hypercube_dim;
}
/**
* Initializes a hypercube corner for a given dimension with specified coordinates.
*
* @param hypercube_dim The dimension of the hypercube corner.
* @param position Decimal type position for the coordinates, converted to binary.
*
* Running time is O(n), where 'n' is the dimension. This method initializes the coordinates array,
* iterating through 'n' elements to set them based on the binary representation of the position.
*/
public Corner(int hypercube_dim, int position) {
this(hypercube_dim); // call to another constructor for initializing hypercube dimension
for (int i = hypercube_dim - 1; i >= 0; i--) {
this.coordinates[i] = ((position & 1) == 1); // set coordinates based on binary representation of position
position >>= 1; // right shift position by 1 bit to move to the next bit
}
}
/**
* Move one step in a specific dimension.
*
* @param dimensionToMove The dimension in which to move.
*
* Running time is O(1). This method performs a constant-time operation by toggling the coordinate value.
*/
public void flipCoordinate(int dimensionToMove) {
this.coordinates[dimensionToMove] ^= true; // toggle the coordinate value
}
/* *************** toString *********************** */
/**
* Convert the boolean coordinates to a binary String.
*
* @return A binary string representing the hypercube corner's coordinates.
*
* Running time is O(n), where 'n' is the dimension. This method constructs a binary string by iterating
* through 'n' coordinates to convert them to '0' or '1'.
*/
@Override
public String toString() {
StringBuilder stb = new StringBuilder();
for (boolean coordinate : this.coordinates) stb.append(coordinate ? 1 : 0);
return stb.toString();
}
/**
* Extends a Corner object by adding a new dimension.
*
* @param origCnr The original Corner object.
* @param position The new dimension's position.
* @return A new Corner object with an increased dimension.
*
* Running time is O(n), where 'n' is the new dimension. This method creates a new Corner object with
* an updated dimension and copies the existing coordinates, involving iterating through 'n' coordinates.
*/
public static Corner extendCorner(Corner origCnr, boolean position) {
// Create a new Corner object with an increased dimension
Corner newCnr = new Corner(origCnr.hypercube_dim + 1);
// Copy the existing coordinates from the original Corner to the new Corner
int index = 0;
for (boolean coordinate : origCnr.coordinates) {
newCnr.coordinates[index++] = coordinate;
}
// Set the coordinates of the new dimension based on the 'position' parameter
newCnr.coordinates[origCnr.hypercube_dim] = position;
// Return the new Corner object with the increased dimension
return newCnr;
}
}
/* RECURSIVE METHOD */
//--- RECURSIVE ALGORITHM CORRECTNESS PROOF ---//
/*
* We establish the correctness of the recursive algorithm for generating hypercube corners
* using the following notation:
*
* Pre-Cond: 'n' represents the current dimension being processed, and 'currentCnr' is the current corner.
*
* <ALGORITHM> corresponds to the 'recursiveWalk(n)' method. It explores the left
* and right children of the current corner in the hypercube recursively until the specified dimension
* is reached.
*
* Post-Cond: The method correctly generates and prints all possible hypercube corners for the given 'n' dimension.
*/
/********************** Proof by Strong Induction *********************/
/* We apply strong induction on the dimension 'n' for each recursive call. */
/********** Base Case ***********/
/* The algorithm correctly handles base cases where 'n' becomes 0, and the corner is printed. */
/********** Inductive Step ***********/
/* Assuming that for any valid dimension 'n', the 'recursiveWalk' method correctly
* transitions from its own pre-condition to its own post-condition by exploring left and right
* children of the current corner in the hypercube recursively until 'n' reaches 0. */
/********** Chaining Assumptions ***********/
/* These correctness proofs are combined with the remaining code to ensure that
* at each recursion level, the algorithm effectively explores and prints all potential hypercube corners
* for the current 'n' dimension.
*/
/********** Conclusions ***********/
/* By employing strong induction and connecting these correctness proofs, we establish that the
* primary call to 'recursiveWalk(n)' correctly transitions from its initial pre-condition to its ultimate
* post-condition. This guarantees the accurate generation and printing of all possible hypercube corners for
* the provided 'n' dimension.
// This proof validates the correctness of the recursive algorithm for generating hypercube corners
// for all conceivable dimensions 'n', providing a robust and reliable solution.
*/
/**
* This method generates hypercube corners using a recursive approach.
*
* @param hypercube_dim The dimension of the hypercube.
*
* Running time O(2^n), where 'n' is the dimension of the hypercube. This is because, in each step, the method branches
* into two recursive calls, effectively creating a binary tree with a depth of 'n'. As a result, the total number of
* calls is proportional to 2^n.
*
* @see Corner
*/
public void recursiveWalk(int hypercube_dim) {
Corner initialCnr = new Corner(hypercube_dim); // initialize the initial corner, and print
this.traverseHypercube(hypercube_dim, initialCnr); // launch recursion
}
/**
* This is a helper method for the recursive approach, used to traverse the hypercube corners.
*
* @param n Specifies the current dimension being processed.
* @param currentCnr The current corner in the hypercube system.
*
* This method is a recursive helper function for the `recursiveWalk` method. It explores the left
* and right children of the current corner in the hypercube recursively until the specified dimension
* is reached. At each step, it toggles one dimension to traverse the binary tree of hypercube corners.
*
* Running time is O(1) for each call. However, it is called recursively
* for each dimension, which results in O(n) total time complexity, where 'n' is the dimension.
*
* @see Corner
*/
private void traverseHypercube(int n, Corner currentCnr) {
if (n == 0) { System.out.println(currentCnr.toString()); return; } // base case: When the dimension reaches zero, print the corner
else if (n > 0) {
this.traverseHypercube(n - 1, currentCnr); // explore the left child of the node
currentCnr.flipCoordinate(n - 1); // move one step in the current dimension
this.traverseHypercube(n - 1, currentCnr); // explore the right child of the node
}
}
/* ITERATIVE METHOD */
/**
* Generates and prints hypercube corners iteratively for dimensions from 1 to 'n'.
*
* @param hypercube_dim The dimension of the hypercube.
*
* This method constructs hypercube corners iteratively, starting from dimension 1 up to the specified dimension 'n'.
* It prints the generated hypercube corners for dimension 'n'.
*
* Running time complexity is O(n * 2^n). In the worst case, it generates and processes 2^n corners for each dimension
* (from 1 to 'n'). For each corner, it performs constant time operations (enqueueing, dequeuing),
* resulting in the aforementioned time complexity.
*
*/
public void iterativeWalk(int hypercube_dim) {
// Initialize the starting point and print
ArrayDeque<Corner> cnrQueue = new ArrayDeque<Corner>();
// INITIALIZE: Set the queue with the solution for n = 1
cnrQueue.offer(new Corner(1, 0));
cnrQueue.offer(new Corner(1, 1));
boolean order = true;
// ITERATE: Incrementally & inductively maintain the Loop Invariant shown below:
while (!cnrQueue.isEmpty()) {
/* LOOP INVARIANT: At the end of this iteration, 'cornerQueue' contains valid corners for the current
* dimension, 'order' correctly alternates for enqueueing, and 'currentCnr' represents a valid
* hypercube corner.
*/
Corner currentCnr = cnrQueue.poll();
// If the current corner is of the specified dimension, print it
if (currentCnr.hypercube_dim == hypercube_dim) {
System.out.println(currentCnr.toString());
} else {
// Enqueue the next level corners, alternating between left and right
cnrQueue.offer(order ? Corner.extendCorner(currentCnr, false) :
Corner.extendCorner(currentCnr, true));
cnrQueue.offer(order ? Corner.extendCorner(currentCnr, true) :
Corner.extendCorner(currentCnr, false));
order ^= true; // toggle the order for the next level
}
}
}
/* MAIN */
/**
* main() runs some test cases on the above Hypercube methods.
*/
public static void main(String[] args) {
Hypercube hypercube = new Hypercube();
int n = 0;
Scanner in = new Scanner(System.in);
while (n <= 0) {
System.out.print("Please enter the dimension of the hypercube (a positive integer): ");
n = in.nextInt();
if (n <= 0) {
System.out.println("INVALID DIMENSION: " + n + ". Dimension must be a positive integer");
}
}
in.close();
System.out.println("\n");
System.out.println("recursiveWalk()"); hypercube.recursiveWalk(n);
System.out.println("iterativeWalk()"); hypercube.iterativeWalk(n);
}
}