Let $S$ be a subset of $[0,1]^l$. Is there some data structure that can represent $S$ and can perform the following operations/queries efficiently*?

  1. $ADD(s \in [0,1]^l)$ - operation which updates $S$ to become $S\cup \{s\}$
  2. $REMOVE(s \in [0,1]^l)$ - operation which updates $S$ to become $S \setminus \{s\}$
  3. $PERMUTE(\sigma)$ - operation which updates $S$ to become $\{\sigma(s) : s \in S\}$, where sigma is a permutation of $s$, which rearranged its indices/letters according to a bijection
  4. $START(t \in [0,1]^k)$ - query which returns whether or not there is a string $s \in S$ whose first $k$ letters are the same as $t$

*By efficiently, I mean that it can perform each of the above with worst case complexity $c^{o(l)}$. In other words, I am fine with complexity that is exponential, but I want the exponent to be sublinear in $l$.

A simple prefix tree can do 1, 2, and 4 all linear in $l$, but I can't fathom that it can efficiently do 3. However, if you needed to only support 4 for substrings up to length $k$, we could keep track of how are indices have been permuted since the beginning, and just have $k!\binom{l}{k}$ prefix-trees for each way that could start, which would make 3 and 4 linear, and 1 and 2 $O(l^k)$.

  • $\begingroup$ You don’t actually permute the array. You just store and update the permutation, and only access the array through it. $\endgroup$ – Yuval Filmus Aug 30 '19 at 18:58
  • $\begingroup$ @Yuval Filmus if all my arrays end in "0", and we swap the first and last indices, I'd have to explore every leaf before I got my answer to $START(1)$ $\endgroup$ – Zachary Hunter Aug 30 '19 at 19:11
  • $\begingroup$ What class of maps $\sigma$ do you want to support? How is $\sigma$ represented? $\endgroup$ – D.W. Aug 30 '19 at 19:24
  • $\begingroup$ A map $\sigma$ will be a bijection on the indices $1,2 \dots l \to 1,2 \dots l $. I wish to support all such maps/permutations $\sigma$. You can choose to use whichever representation of $\sigma$ you desire. $\endgroup$ – Zachary Hunter Aug 30 '19 at 19:33
  • 1
    $\begingroup$ Have you tried to apply range trees? $\endgroup$ – Dmitri Urbanowicz Sep 3 '19 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.