The $O!)$ complexity for permutation generation is back…
0 reactions
The $O!)$ complexity for permutation generation is back. Do you believe it now?
<===**Ignoring the output cost===**\>
I’m here to challenge the status quo once again: The control overhead of permutation generation can be reduced from O(n!) to O((n-1)!).
I know the total number of permutations is $n!$, but here is the real question: Why on earth should your control flow also run $n!$ times just to output $n!$ results?
**Core Idea:**
The DPP (Dual Position Pure) algorithm uses a "Dual-Ring Topology" to fold the state space from n down to n-1.
**Logic:** Construct two in-place permutation structures (it works with Heap's, SJT, or PP) and bridge them with a central element.
**Emergence:** Think of it like this:(0, 1, 2)< 3>(0, 1, 2). A single pass through the 3-element permutation generates the 4-element permutations: 0123, 1230, 2301, 3012.
then "emerge" the full set of $n$-element permutations. **Ignoring the output cost,** the control overhead is effectively limited to 2\*(n-1) in terms of complexity, rather than $n!$.
I’d love to get your thoughts on this approach. **I also didn't expect that a structural improvement would render an algorithmic improvement meaningless.**
#technology
<===**Ignoring the output cost===**\>
I’m here to challenge the status quo once again: The control overhead of permutation generation can be reduced from O(n!) to O((n-1)!).
I know the total number of permutations is $n!$, but here is the real question: Why on earth should your control flow also run $n!$ times just to output $n!$ results?
**Core Idea:**
The DPP (Dual Position Pure) algorithm uses a "Dual-Ring Topology" to fold the state space from n down to n-1.
**Logic:** Construct two in-place permutation structures (it works with Heap's, SJT, or PP) and bridge them with a central element.
**Emergence:** Think of it like this:(0, 1, 2)< 3>(0, 1, 2). A single pass through the 3-element permutation generates the 4-element permutations: 0123, 1230, 2301, 3012.
then "emerge" the full set of $n$-element permutations. **Ignoring the output cost,** the control overhead is effectively limited to 2\*(n-1) in terms of complexity, rather than $n!$.
I’d love to get your thoughts on this approach. **I also didn't expect that a structural improvement would render an algorithmic improvement meaningless.**
#technology
| 3,000 mlx | |
| 5 | |
| 0 |