Original Post
Hi, a short description of my problem: I'd like to check, if a given set is a sub- or supersets of a set previously stored (or if a set is equal to a previously stored set). And I'd like to do that fast. I have researched tries and treaps for string- and substring search and they seem to be appropriate. But please let me elaborate (there's an example at the bottom of the gibberish explanation) and give me your opinions: At the start of the algorithm, I have an ordered list of numbers from 1 to n. Those numbers are split into subsets and those subsets are then passed to a "do-a-very-complicated-calculation" method which returns an integer value (actually it returns either 0, 1, or 2). Depending on the result of the calculation, the subsets are refined (and rearranged: split or merged). In the course of the calculation it might arise that a set that has already been processed is processed again, so now I need a fast way of detecting (storing) if a set has already been tested. Furthermore, I can assume that if the result of a set s is 0 then any subset of s will also return 0 and I can assume that a result of 2 for s means that any superset of s will also return 2. Question is: Do you know a data structure which could be used to model the above situation? Can you point me to resources? (As stated above: Right now I think treaps or tries are the way to go. Agree? Disagree?) Please also note that I cannot generate the structure before I do the calculation. That is, I cannot generate my tree (or whatever structure) and fill it with content and simply look it up on runtime---I'd have to store about a terabyte of data only for those trees... :) Example for a calculation: Initial set: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1st round: {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10} 2nd round: {1, 2, 3}, {4, 5}, {6, 7, 8}, {9, 10} 3rd round: {1, 2}, {3, 4, 5}, {6, 7}, {8, 9, 10} 4th round: {1}, {2, 3}, {4, 5}... And there you go (although I agree: It does not seem to be deterministic how the sets are generated :), I can assure you that there is a rule behind it). The important point is that the set (4, 5) is tested twice here (and since there's a total of 72 rounds for this example, _many_ combinations are tested over and over again). Well---any ideas? Thanks for your help!! Beren
