<p>If it can be done with heaps why not Young Tableaux? <sup>[1]</sup></p>
<p>I know that the analogy is too simplistic but for learning sake, let us consider it.</p>
<p>The only limitation I noticed is that while heaps exhibit <em>local dependencies</em>, Young Tableaux have <em><strong>strong</strong> global dependencies</em>. <sup>[2]</sup></p>
<p>But independent of this, someone might have already done it. Is it possible and if so, how? If not, give an objective reason why not (possibly with proofs if you can). <sup>[3]</sup></p>
<hr/>
<p><sub><sup>[1]</sup> Arrays can be given heap property in <em>O(1)</em> space.</sub></p>
<p><sub><sup>[2]</sup> The term <em>&quot;local dependencies&quot;</em> as used with reference to heaps is because dependent relationships only spawn between parent and child. In Young Tableaux,  dependent relationships spawn across rows and columns. Hence my use of the term <em>&quot;global dependencies&quot;</em>.</sub></p>
<p><sub><sup>[3]</sup> We all know that opinions will not help so for posterity sake, let’s stick with objective reasons.</sub></p>

CC BY-SA 4.0
2024-07-28T06:49:40.697Z
I am writing an article and I made such a bold statement but cannot back it up which got me stuck so I need help figuring this one out. Thank you for your time.
Chukwujiobi Canon
CC BY-SA 4.0
2024-07-28T12:36:13.863Z
I am familiar with the definition of Young tabeaux, but I have hard time understanding the question. What do you mean by "giving Young tabeau property" to a matrix?
Vladimir Lysikov
CC BY-SA 4.0
2024-07-28T13:11:12.223Z
Turning a matrix into a Young Tableau. In programming we say we have given it a particular property. Technically it is still a matrix but now has a certain property — *Young Tableau*.
Chukwujiobi Canon
CC BY-SA 4.0
2024-07-28T13:14:40.093Z
Yes, but which operations are you allowed to use for that? I can turn any matrix into a Young tableau by writing the elements from 1 to $mn$ into the matrix in the right order
Vladimir Lysikov
CC BY-SA 4.0
2024-07-28T17:42:43.317Z
I thought so too. But I think that while that is space optimal, it is not time optimal. Nonetheless that answers the question with lingering concern for time complexity.
Chukwujiobi Canon
<ds.algorithms><ds.data-structures>
Can an m * n matrix be given Young Tableau property in O(1) space?
Chukwujiobi Canon
# Can an m * n matrix be given Young Tableau property in O(1) space?

(Asked by: username_0 on 2024-07-28)

If it can be done with heaps why not Young Tableaux? [1]

I know that the analogy is too simplistic but for learning sake, let us consider it.

The only limitation I noticed is that while heaps exhibit *local dependencies*, Young Tableaux have ***strong** global dependencies*. [2]

But independent of this, someone might have already done it. Is it possible and if so, how? If not, give an objective reason why not (possibly with proofs if you can). [3]

---

[1] Arrays can be given heap property in *O(1)* space.

[2] The term *"local dependencies"* as used with reference to heaps is because dependent relationships only spawn between parent and child. In Young Tableaux, dependent relationships spawn across rows and columns. Hence my use of the term *"global dependencies"*.

[3] We all know that opinions will not help so for posterity sake, let’s stick with objective reasons.

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_0**: I am writing an article and I made such a bold statement but cannot back it up which got me stuck so I need help figuring this one out. Thank you for your time.  
> **username_1**: I am familiar with the definition of Young tabeaux, but I have hard time understanding the question. What do you mean by "giving Young tabeau property" to a matrix?  
> **username_0**: Turning a matrix into a Young Tableau. In programming we say we have given it a particular property. Technically it is still a matrix but now has a certain property — *Young Tableau*.  
> **username_1**: Yes, but which operations are you allowed to use for that? I can turn any matrix into a Young tableau by writing the elements from 1 to $mn$ into the matrix in the right order  
> **username_0**: I thought so too. But I think that while that is space optimal, it is not time optimal. Nonetheless that answers the question with lingering concern for time complexity.  

---

## 0 answers

