Timeline for Finding containing sets in a set of sets
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2020 at 2:37 | history | edited | xskxzr | CC BY-SA 4.0 |
deleted 18 characters in body
|
| Jan 3, 2013 at 1:54 | history | tweeted | twitter.com/#!/StackCompSci/status/286651839410229249 | ||
| Jan 2, 2013 at 19:58 | answer | added | Paresh | timeline score: 2 | |
| Jan 2, 2013 at 19:26 | comment | added | Realz Slaw | @Paresh Consider the integer sets static, but adding removing from them is equivalent to removing the set, adding the element, and reinserting it. | |
| Jan 2, 2013 at 19:23 | comment | added | Paresh | @RealzSlaw I meant adding or removing elements/integers from sets in $A$. I'll chalk out an answer with more details. | |
| Jan 2, 2013 at 19:03 | comment | added | Realz Slaw | @Paresh If you have a method that takes advantage of it being $A$ being static, I'd like to hear it as long as you specify as such. I don't know what you mean about the sets in $A$ being dynamic though, that is equivalent to removing the set, and inserting another, unless I am misunderstanding the question. | |
| Jan 2, 2013 at 18:58 | comment | added | Paresh | Are the sets inside $A$ (the set of sets) dynamic? | |
| Jan 2, 2013 at 17:42 | comment | added | AJed | @KarolisJuodelė exactly! trie is the word i was looking for. | |
| Jan 2, 2013 at 17:41 | comment | added | AJed | I would think of it as a set of strings. Use something similar to a suffix tree. (look at this: en.wikipedia.org/wiki/Generalised_suffix_tree). For instance, a tree rooted at $\emptyset$. Every node has at most 10 children. You would include a set $\{1,2,3\}$ for example starting by inserting 1 as a child of the root, 2 as a child 1 etc .. i think you can solve it efficiently with something like this, but you need to take care of details. | |
| Jan 2, 2013 at 17:40 | comment | added | Karolis Juodelė | This is already somewhat $O(n)$. Building the structure will surely take longer. Though if you need to perform this operation repeatedly, have you considered a plain old trie? | |
| Jan 2, 2013 at 16:29 | history | edited | Realz Slaw | CC BY-SA 3.0 |
edited body
|
| Jan 2, 2013 at 15:45 | history | edited | A.Schulz | CC BY-SA 3.0 |
added tags, formating
|
| Jan 2, 2013 at 15:40 | history | edited | Realz Slaw | CC BY-SA 3.0 |
edited body
|
| Jan 2, 2013 at 15:28 | history | asked | Realz Slaw | CC BY-SA 3.0 |