# Given a partition and an element, find the subset that includes this element

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

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$$.

• 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. Apr 7, 2021 at 3:26
• @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.
– D.W.
Apr 7, 2021 at 7:22