I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am mostly interested in some general background on this problem. I'm stuck because I do not know of a canonical "name" for this problem.

Does this problem have a name, or is there a closely related problem that might generate some useful hits?


1 Answer 1


It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.

  • $\begingroup$ The problem is to compute this map. Of course if the map is known this is trivial. Furthermore, many problems in TCS "have" solutions, and yet are still the subject of intense research. $\endgroup$
    – user77463
    Apr 7, 2021 at 3:26
  • 1
    $\begingroup$ @user77463, I can only answer the question that was stated. With the standard way to represent a partition, computing the map from the representation is trivial. If you are representing the partition in some specific way, then I suggest asking a new question, and specify exactly how the partition is represented, and tell us what is the best algorithm you have found so far. If it's not research-level, it belongs on CS.SE, not here. $\endgroup$
    – D.W.
    Apr 7, 2021 at 7:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.