Saeven
March 19th, 2008, 08:13 PM
Am perusing through old assignments, and I can't recall what data structure, this array representation is a reflection of. Any guru ideas appreciated!
setup
- given a set of real numbers, X
- let n be the size of the set X
- write n in binary
usage
Partition the set X into subsets such that there is one subset X_i of size 2^i, for each i for which a_i was 1 in the binary format of the size of X.
ex. n = 87
= 2^0 + 2^1 + 2^2 + 2^4 + 2^6
so X is partitioned into five subsets having sizes 1, 2, 4, 16, and 64.
lastly
For each i for which a_i = 1, we sort the elements of the subset X_i and store the sorted sequence in an array A_i[1....2^i]
Ring a bell? It's a headcracker!
Cheers.
Alex
setup
- given a set of real numbers, X
- let n be the size of the set X
- write n in binary
usage
Partition the set X into subsets such that there is one subset X_i of size 2^i, for each i for which a_i was 1 in the binary format of the size of X.
ex. n = 87
= 2^0 + 2^1 + 2^2 + 2^4 + 2^6
so X is partitioned into five subsets having sizes 1, 2, 4, 16, and 64.
lastly
For each i for which a_i = 1, we sort the elements of the subset X_i and store the sorted sequence in an array A_i[1....2^i]
Ring a bell? It's a headcracker!
Cheers.
Alex