<p>See chapter 3 of Nijenhuis and Wilf, "<a href="http://www.math.upenn.edu/~wilf/website/CombAlgDownld.html" rel="nofollow">Combinatorial Algorithms</a>" (the entire book is available free online and despite its age contains many useful algorithms).</p>

CC BY-SA 3.0
2011-06-15T07:53:09.113Z
2011-06-15T07:53:09.113Z
David Eppstein
<p>Suppose you are given an $n$-dimensional simplex</p>

<pre><code>S = [ 0 1 ... n ]
</code></pre>

<p>which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given $1 \leq k \leq n$, how can we enumerate the $k$-faces of S, i.e. the $k$-dimensional subsimplices? - In less geometric words, we want a complete and multiples-free list of all $k$-sized strictly ascending sequences of numbers between in $\{ 0, \dots , n \}$.</p>

<p>The straight-forward algorithm is to create the list of all $k$-sized tuples of numbers between $0$ and $n$, and pop out those that are not strictly ascending or contain duplicates. This can be done in space and time $O(n^3)$.</p>

<p>But can we do better? We do not impose restrictions on a particular ordering of the output.</p>

CC BY-SA 3.0
2011-06-15T14:43:35.827Z
There are about $O(n^k)$ subsimplices. How do you get them in time $O(n^3)$ for $k>3$? Do you have $k=3$ or did you mean $O(n^k)$?
j.p.
CC BY-SA 3.0
2011-06-15T14:50:20.990Z
For the implementation: Do you mind a simple recursion $S(n, k) = \cup_{i=k-1\dots n} (S(i-1, k-1)+\{i\})$, where $+$ denotes joining the singleton set $\{i\}$ to each simplex in the list/set $S(i-1, k-1)$ of $(k-1)$-subsimplices of $\[0 1 \dots i-1\]$?
j.p.
<cg.comp-geom><permutations>
List the $k$-faces of an $n$-dimensional simplex
shuhalo
# List the $k$-faces of an $n$-dimensional simplex

(Asked by: username_0 on 2011-06-15)

Suppose you are given an $n$-dimensional simplex
S = [ 0 1 ... n ]

which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given $1 \leq k \leq n$, how can we enumerate the $k$-faces of S, i.e. the $k$-dimensional subsimplices? - In less geometric words, we want a complete and multiples-free list of all $k$-sized strictly ascending sequences of numbers between in $\{ 0, \dots , n \}$.
The straight-forward algorithm is to create the list of all $k$-sized tuples of numbers between $0$ and $n$, and pop out those that are not strictly ascending or contain duplicates. This can be done in space and time $O(n^3)$.
But can we do better? We do not impose restrictions on a particular ordering of the output.

**Tags:** cg.comp-geom, permutations

> **Comments:**
> **username_1**: There are about $O(n^k)$ subsimplices. How do you get them in time $O(n^3)$ for $k>3$? Do you have $k=3$ or did you mean $O(n^k)$?  
> **username_1**: For the implementation: Do you mind a simple recursion $S(n, k) = \cup_{i=k-1\dots n} (S(i-1, k-1)+\{i\})$, where $+$ denotes joining the singleton set $\{i\}$ to each simplex in the list/set $S(i-1, k-1)$ of $(k-1)$-subsimplices of $\[0 1 \dots i-1\]$?  

---

## 1 answers

### Answer by username_2 on 2011-06-15. Score: 3 | Accepted answer

See chapter 3 of Nijenhuis and Wilf, "[Combinatorial Algorithms](http://www.math.upenn.edu/~wilf/website/CombAlgDownld.html)" (the entire book is available free online and despite its age contains many useful algorithms).


---

