<p>It is unlikely to have a &quot;name&quot; because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps <span class="math-container">$x$</span> to <span class="math-container">$X_i$</span>.</p>

CC BY-SA 4.0
2021-04-07T03:26:46.753Z
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.
user77463
CC BY-SA 4.0
2021-04-07T07:22:28.377Z
@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.
CC BY-SA 4.0
2021-04-06T03:21:26.177Z
2021-04-06T03:21:26.177Z
D.W.
<p>I am interested in the following simple problem: Let <span class="math-container">$X$</span> be a set and <span class="math-container">$X_1\cup X_2\cup\cdots\cup X_k$</span> be a finite partition of <span class="math-container">$X$</span>. Given <span class="math-container">$x\in X$</span>, find the subset <span class="math-container">$X_i$</span> for which <span class="math-container">$x\in X_i$</span>. I am mostly interested in some general background on this problem. I'm stuck because I do not know of a canonical &quot;name&quot; for this problem.</p>
<p>Does this problem have a name, or is there a closely related problem that might generate some useful hits?</p>

CC BY-SA 4.0
2021-04-05T17:39:19.857Z
You might be interested in this: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Denis
<cc.complexity-theory><ds.algorithms><reference-request><set-theory>
Given a partition and an element, find the subset that includes this element
user77463
# Given a partition and an element, find the subset that includes this element

(Asked by: username_0 on 2021-04-05)

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?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, set-theory
> **Comments:**
> **username_1**: You might be interested in this: https://en.wikipedia.org/wiki/Disjoint-set_data_structure  

---

## 1 answers

### Answer by username_2 on 2021-04-06. Score: 2

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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.  

---

