perm

Documentation

Overview

Package perm provides permutation generation algorithms and the PQ-tree data structure for constrained ordering problems.

Overview

Finding the optimal row ordering in a layered graph is NP-hard—the number of possible orderings grows factorially with row size. This package provides tools to make this tractable:

• PQTree: A data structure that compactly represents families of valid permutations, allowing massive pruning of the search space
• Generate: Efficient permutation generation with optional limits
• Factorial: Helper for combinatorial calculations

The PQ-Tree

A PQ-tree represents a set of permutations that satisfy "consecutive ones" constraints. If elements {A, B, C} must appear consecutively (in any order), the PQ-tree encodes only those permutations where they do.

The tree has two types of internal nodes:

• P-nodes (Permutable): Children can be arranged in any order (n! orderings)
• Q-nodes (seQuence): Children have a fixed order, but can be reversed (2 orderings)

How It Works

Consider 5 nodes with a constraint that {1, 2, 3} must be consecutive:

Without PQ-tree: 5! = 120 permutations to check
With PQ-tree:    3! × 3! × 2 = 72 valid permutations

As more constraints are applied, the valid count shrinks dramatically. For dependency graphs with strong structure (chains, hierarchies), PQ-trees often reduce millions of permutations to just a few hundred.

Basic Usage

Create a tree, apply constraints via PQTree.Reduce, then enumerate valid orderings:

tree := perm.NewPQTree(5)  // 5 elements: 0, 1, 2, 3, 4

// Elements 1, 2, 3 must be consecutive
tree.Reduce([]int{1, 2, 3})

// Elements 0, 1 must be consecutive
tree.Reduce([]int{0, 1})

// Get all valid orderings (or first N with a limit)
orderings := tree.Enumerate(100)

If a constraint is impossible to satisfy, PQTree.Reduce returns false, allowing early termination of search branches.

Permutation Generation

For small sets or when PQ-tree constraints don't apply, use Generate for efficient permutation enumeration:

// All 24 permutations of 4 elements
all := perm.Generate(4, -1)

// First 100 permutations of 10 elements (for sampling)
sample := perm.Generate(10, 100)

In the Ordering Pipeline

The ordering algorithms in render/tower/ordering use PQ-trees to encode:

• Chain constraints: Subdivider nodes sharing a MasterID must stay together
• Parent constraints: Children of the same parent should be adjacent
• Child constraints: Parents of the same child should be adjacent

This dramatically reduces the search space for the branch-and-bound algorithm that finds optimal or near-optimal orderings.

render/tower/ordering: github.com/stacktower-io/stacktower/pkg/core/render/tower/ordering

Index

• func Factorial(n int) int
• func Generate(n, limit int) [][]int
• func Seq(n int) []int
• type PQTree
  • func NewPQTree(n int) *PQTree
  • func (t *PQTree) Clone() *PQTree
  • func (t *PQTree) Enumerate(limit int) [][]int
  • func (t *PQTree) EnumerateFunc(fn func([]int) bool) int
  • func (t *PQTree) Reduce(constraint []int) bool
  • func (t *PQTree) RenderSVG(labels []string) ([]byte, error)
  • func (t *PQTree) String() string
  • func (t *PQTree) StringWithLabels(labels []string) string
  • func (t *PQTree) ToDOT(labels []string) string
  • func (t *PQTree) ValidCount() int

Examples

• Factorial
• Generate
• Generate (Limited)
• PQTree (Basic)
• PQTree (Impossible)
• PQTree.Clone
• PQTree.Enumerate
• PQTree.EnumerateFunc
• PQTree.Reduce
• PQTree.String
• PQTree.StringWithLabels
• Seq

Functions

func Factorial

func Factorial(n int) int

Factorial returns n! (n factorial), the product 1 × 2 × ... × n. For n <= 1, Factorial returns 1.

This function is useful for calculating the size of the full permutation space. Note that factorials grow extremely fast: 13! = 6,227,020,800 exceeds 32-bit int.

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	fmt.Println("4! =", perm.Factorial(4))
	fmt.Println("5! =", perm.Factorial(5))
}

Output:
4! = 24
5! = 120

func Generate

func Generate(n, limit int) [][]int

Generate returns permutations of [0, 1, ..., n-1] using Heap's algorithm.

If limit > 0, Generate returns at most limit permutations. If limit <= 0, Generate returns all n! permutations.

Each returned slice is a separate allocation, safe to modify without affecting others.

Generate handles edge cases gracefully:

• n = 0: returns [[]] (one empty permutation)
• n = 1: returns [[0]] (one single-element permutation)

For n >= 13, the number of permutations exceeds billions. Always use a limit when n is large, or your program will exhaust memory.

Heap's algorithm generates permutations in a non-lexicographic order, but efficiently produces each permutation exactly once.

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// Generate all permutations of 3 elements
	perms := perm.Generate(3, -1)
	fmt.Println("All permutations of [0,1,2]:")
	for _, p := range perms {
		fmt.Println(p)
	}
}

Output:
All permutations of [0,1,2]:
[0 1 2]
[1 0 2]
[2 0 1]
[0 2 1]
[1 2 0]
[2 1 0]

Example (Limited)

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// Generate only the first 5 permutations of 10 elements
	perms := perm.Generate(10, 5)
	fmt.Println("Count:", len(perms))
}

Output:
Count: 5

func Seq

func Seq(n int) []int

Seq returns a slice containing the sequence [0, 1, 2, ..., n-1]. This is useful for initializing permutation arrays or creating index sequences.

For n <= 0, Seq returns an empty slice.

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// Create a sequence [0, 1, 2, ..., n-1]
	seq := perm.Seq(5)
	fmt.Println(seq)
}

Output:
[0 1 2 3 4]

Types

type PQTree

type PQTree struct {
	// contains filtered or unexported fields
}

PQTree is a data structure that compactly represents a family of permutations satisfying "consecutive ones" constraints.

A PQ-tree encodes the valid orderings of n elements where certain subsets must appear consecutively. The tree represents all permutations that satisfy the applied constraints, allowing efficient pruning of invalid orderings.

The tree has two types of internal nodes:

• P-nodes (Permutable): children can appear in any order (n! orderings)
• Q-nodes (seQuence): children have a fixed order, reversible (2 orderings)

PQTree is not safe for concurrent use. If multiple goroutines access a PQTree, they must be synchronized with external locking.

The zero value of PQTree is not usable; use NewPQTree to create instances.

Example (Basic)

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// Create a PQ-tree for 5 elements
	tree := perm.NewPQTree(5)

	// Without constraints: all 5! = 120 permutations are valid
	fmt.Println("Before constraints:", tree.ValidCount())

	// Require {1, 2, 3} to be consecutive
	tree.Reduce([]int{1, 2, 3})
	fmt.Println("After {1,2,3} consecutive:", tree.ValidCount())
}

Output:
Before constraints: 120
After {1,2,3} consecutive: 36

Example (Impossible)

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// Some constraint combinations are impossible
	tree := perm.NewPQTree(4)

	// {0, 1} consecutive and {2, 3} consecutive
	tree.Reduce([]int{0, 1})
	tree.Reduce([]int{2, 3})

	// Now try: {1, 2} consecutive (impossible - would require 0,1,2,3 all consecutive)
	// Actually this IS possible: [0 1 2 3] or [3 2 1 0], etc.
	// Let's try a truly impossible case:
	tree2 := perm.NewPQTree(4)
	tree2.Reduce([]int{0, 2}) // 0 and 2 must be adjacent
	tree2.Reduce([]int{1, 3}) // 1 and 3 must be adjacent

	// Now require 0 and 1 adjacent - impossible since 0 is paired with 2, and 1 with 3
	ok := tree2.Reduce([]int{0, 1})
	fmt.Println("Contradictory constraint:", !ok)
}

Output:
Contradictory constraint: true

func NewPQTree

func NewPQTree(n int) *PQTree

NewPQTree creates a PQ-tree representing all n! permutations of n elements.

The elements are numbered [0, 1, ..., n-1]. Initially, no constraints are applied, so all n! orderings are valid. Call Reduce to apply consecutive-ones constraints that restrict the set of valid permutations.

For n = 0, NewPQTree returns a tree representing one empty permutation. For n = 1, NewPQTree returns a tree with a single element.

The returned PQTree is ready to use and can be modified with Reduce or queried with Enumerate, ValidCount, and String methods.

To explore multiple constraint branches without mutating the original tree, use Clone to create independent copies.

func (*PQTree) Clone

func (t *PQTree) Clone() *PQTree

Clone creates an independent deep copy of the PQ-tree.

The cloned tree has identical structure and represents the same set of valid permutations, but can be modified independently without affecting the original. This is useful for exploring multiple constraint branches in search algorithms.

Clone copies the entire internal tree structure. For large trees, this operation may be expensive. Consider cloning only when necessary.

Example:

tree := perm.NewPQTree(5)
tree.Reduce([]int{1, 2, 3})

// Try two different additional constraints
branch1 := tree.Clone()
branch1.Reduce([]int{0, 1})  // Branch 1 constraint

branch2 := tree.Clone()
branch2.Reduce([]int{3, 4})  // Branch 2 constraint

// Original tree unchanged
fmt.Println(tree.ValidCount())

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	tree := perm.NewPQTree(4)
	tree.Reduce([]int{0, 1})

	// Try different constraints on branches
	branch1 := tree.Clone()
	branch1.Reduce([]int{2, 3})

	branch2 := tree.Clone()
	branch2.Reduce([]int{1, 2})

	fmt.Println("Original:", tree.ValidCount())
	fmt.Println("Branch 1:", branch1.ValidCount())
	fmt.Println("Branch 2:", branch2.ValidCount())
}

Output:
Original: 12
Branch 1: 8
Branch 2: 4

func (*PQTree) Enumerate

func (t *PQTree) Enumerate(limit int) [][]int

Enumerate returns all valid permutations represented by the tree.

If limit > 0, Enumerate returns at most limit permutations. If limit <= 0, Enumerate returns all valid permutations.

Each returned slice is a separate allocation containing element indices in permuted order. The slices are safe to modify without affecting the tree or other returned permutations.

The order of returned permutations is not specified and may change between calls or Go versions.

For trees with a large ValidCount, always use a limit to avoid memory exhaustion. A tree with strong constraints might have only a few hundred valid orderings, while an unconstrained tree has n! orderings.

For memory-efficient streaming without allocating all results at once, use EnumerateFunc instead.

Example:

tree := perm.NewPQTree(4)
tree.Reduce([]int{0, 1, 2})
orderings := tree.Enumerate(10)  // Get first 10 valid orderings

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	tree := perm.NewPQTree(4)

	// Require {0, 1, 2} consecutive
	tree.Reduce([]int{0, 1, 2})

	// Get first 5 valid orderings
	orderings := tree.Enumerate(5)
	fmt.Println("Sample orderings (limit 5):")
	for _, o := range orderings {
		fmt.Println(o)
	}
}

Output:
Sample orderings (limit 5):
[0 1 2 3]
[1 0 2 3]
[2 0 1 3]
[0 2 1 3]
[1 2 0 3]

func (*PQTree) EnumerateFunc

func (t *PQTree) EnumerateFunc(fn func([]int) bool) int

EnumerateFunc generates valid permutations one at a time via callback.

EnumerateFunc calls fn for each valid permutation until fn returns false or all permutations are exhausted. This is memory-efficient for large result sets since permutations are generated on-demand rather than allocated all at once.

The callback fn receives a permutation slice that is valid only for the duration of the call. If the caller needs to retain the permutation, it must copy it (e.g., with slices.Clone).

EnumerateFunc returns the number of permutations processed before stopping. If fn always returns true, the return value equals ValidCount().

The order of generated permutations is not specified and may change between calls or Go versions.

Example:

tree := perm.NewPQTree(10)
tree.Reduce([]int{0, 1, 2, 3, 4})

// Process first 100 permutations without allocating all at once
count := 0
tree.EnumerateFunc(func(perm []int) bool {
	// Process perm here
	fmt.Println(perm)
	count++
	return count < 100  // Stop after 100
})

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	tree := perm.NewPQTree(4)
	tree.Reduce([]int{0, 1, 2})

	// Stream permutations without allocating all at once
	count := 0
	tree.EnumerateFunc(func(perm []int) bool {
		fmt.Println(perm)
		count++
		return count < 3 // Stop after 3
	})
	fmt.Printf("Processed %d permutations\n", count)
}

Output:
[0 1 2 3]
[1 0 2 3]
[2 0 1 3]
Processed 3 permutations

func (*PQTree) Reduce

func (t *PQTree) Reduce(constraint []int) bool

Reduce applies a consecutive-ones constraint to the tree.

After calling Reduce(constraint), only permutations where all elements in constraint appear consecutively (in any order) remain valid. Multiple calls to Reduce apply cumulative constraints, further restricting the valid set.

Reduce returns true if the constraint is satisfiable with previously applied constraints, false if the constraint creates a contradiction. When Reduce returns false, the tree is left in an undefined state and should not be used further.

The constraint slice is not modified. Element indices must be in the range [0, n-1] where n is the value passed to NewPQTree. Out-of-range indices are silently ignored.

Trivial constraints (length 0, 1, or equal to tree size) are always satisfiable and have no effect on the tree structure.

Example:

tree := perm.NewPQTree(5)
tree.Reduce([]int{1, 2, 3})  // Elements 1, 2, 3 must be consecutive
tree.Reduce([]int{0, 1})     // Elements 0, 1 must be consecutive

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// PQ-trees encode "consecutive ones" constraints
	tree := perm.NewPQTree(5)

	// Elements 0, 1 must be consecutive
	ok := tree.Reduce([]int{0, 1})
	fmt.Println("Constraint possible:", ok)

	// Elements 2, 3 must also be consecutive
	ok = tree.Reduce([]int{2, 3})
	fmt.Println("Constraint possible:", ok)

	fmt.Println("Valid orderings:", tree.ValidCount())
}

Output:
Constraint possible: true
Constraint possible: true
Valid orderings: 24

func (*PQTree) RenderSVG

func (t *PQTree) RenderSVG(labels []string) ([]byte, error)

RenderSVG renders the tree structure as an SVG image.

RenderSVG generates a DOT representation via ToDOT, then uses Graphviz to render it to SVG format. The returned bytes are a complete SVG document suitable for embedding in HTML or saving to a file.

The labels parameter is passed to ToDOT and works identically. Pass nil for default numeric labels.

RenderSVG requires the Graphviz library (github.com/goccy/go-graphviz) and its C dependencies to be installed. Errors are returned if Graphviz cannot initialize, the DOT is malformed, or rendering fails.

All errors are wrapped with context using fmt.Errorf with %w, suitable for unwrapping with errors.Unwrap or errors.Is.

The labels slice is not modified.

Example:

tree := perm.NewPQTree(4)
tree.Reduce([]int{1, 2})
svg, err := tree.RenderSVG([]string{"app", "auth", "cache", "db"})
if err != nil {
	log.Fatal(err)
}
os.WriteFile("tree.svg", svg, 0644)

func (*PQTree) String

func (t *PQTree) String() string

String returns a human-readable representation of the tree structure.

The representation uses a nested notation:

• P-nodes (permutable): enclosed in curly braces {}
• Q-nodes (sequence): enclosed in square brackets []
• Leaf nodes: shown as single digits 0-9, or (a), (b), ... for indices >= 10

String is equivalent to StringWithLabels(nil).

Example output: "{0 {1 2 3} 4}" represents a tree where elements 1, 2, 3 must be consecutive but can permute among themselves.

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	tree := perm.NewPQTree(5)

	// P-nodes (permutable) shown with {}, Q-nodes (sequence) with []
	fmt.Println("Initial:", tree.String())

	// Add constraint - groups elements into a P-node (they can be in any order)
	tree.Reduce([]int{1, 2, 3})
	fmt.Println("After constraint:", tree.String())
}

Output:
Initial: {0 1 2 3 4}
After constraint: {0 {1 2 3} 4}

func (*PQTree) StringWithLabels

func (t *PQTree) StringWithLabels(labels []string) string

StringWithLabels returns a human-readable representation using custom labels.

The labels slice maps element indices to strings. If labels[i] exists, element i is displayed as labels[i] instead of its numeric index. This is useful for showing meaningful names in debugging output or examples.

If labels is nil or shorter than needed, numeric indices are used as fallback. The labels slice is not modified.

Example:

tree := perm.NewPQTree(3)
labels := []string{"app", "auth", "db"}
tree.Reduce([]int{0, 1})
fmt.Println(tree.StringWithLabels(labels))  // "{app auth} db" (or similar)

Example

package main

import (
	"fmt"

	"github.com/stacktower-io/stacktower/pkg/core/dag/perm"
)

func main() {
	// Use meaningful labels instead of indices
	tree := perm.NewPQTree(4)
	labels := []string{"app", "auth", "cache", "db"}

	tree.Reduce([]int{1, 2}) // auth and cache consecutive

	fmt.Println(tree.StringWithLabels(labels))
}

Output:
{app {auth cache} db}

func (*PQTree) ToDOT

func (t *PQTree) ToDOT(labels []string) string

ToDOT returns a Graphviz DOT representation of the tree structure.

The DOT format can be rendered with Graphviz tools (dot, neato, etc.) or programmatically with RenderSVG. The output is a complete DOT digraph with styling suitable for documentation and debugging.

Node representation:

• P-nodes: labeled "P", ellipse shape
• Q-nodes: labeled "Q", box shape
• Leaf nodes: labeled with element value or label, rounded box shape

The labels parameter works the same as in StringWithLabels: if labels[i] exists, element i is shown as labels[i], otherwise as a numeric index. Pass nil to use default numeric labels.

The labels slice is not modified.

Example:

tree := perm.NewPQTree(3)
tree.Reduce([]int{0, 1})
dot := tree.ToDOT([]string{"A", "B", "C"})
// Use 'dot' command or RenderSVG to visualize

func (*PQTree) ValidCount

func (t *PQTree) ValidCount() int

ValidCount returns the number of valid permutations represented by the tree.

ValidCount efficiently computes the count without enumerating all permutations. The count reflects all constraints applied via Reduce.

The count is computed from the tree structure:

• P-nodes multiply by n! (factorial of child count)
• Q-nodes multiply by 2 (forward and reverse)
• Leaf nodes contribute 1

For large trees, the count may be accurate even when Enumerate(0) would exhaust memory. Use ValidCount to check if enumeration is feasible before calling Enumerate without a limit.

Example:

tree := perm.NewPQTree(5)           // 5! = 120 permutations
tree.Reduce([]int{1, 2, 3})
fmt.Println(tree.ValidCount())      // Much less than 120