Introduction

System.OutOfMemoryException during permutation generation is usually not a runtime bug in .NET itself, but a design issue caused by factorial growth. Even moderate input sizes produce more permutations than memory can hold. This guide explains why it happens and how to redesign permutation code to be memory-safe.

Core Topic Sections

Understand the growth first

Number of permutations for n unique elements is n!. That growth is extreme:

1. 10! equals 3,628,800.
2. 12! equals 479,001,600.
3. 15! exceeds one trillion.

If each permutation is stored as a new array, memory usage explodes quickly. The first fix is architectural: do not materialize everything unless input size is tiny.

Why list-based implementations fail

A common pattern builds a nested list structure and appends every permutation. This causes:

1. Huge object allocation count.
2. Frequent garbage collection pressure.
3. Eventual memory exhaustion.

The correct model is stream processing. Generate one permutation, consume it, then move on.

Use iterator-based generation in C#

yield return allows lazy production of permutations.

1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public static class Permutations
6{
7    public static IEnumerable<int[]> Generate(int[] input)
8    {
9        var arr = (int[])input.Clone();
10        Array.Sort(arr);
11        do
12        {
13            yield return (int[])arr.Clone();
14        }
15        while (NextPermutation(arr));
16    }
17
18    private static bool NextPermutation(int[] arr)
19    {
20        int i = arr.Length - 2;
21        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
22        if (i < 0) return false;
23
24        int j = arr.Length - 1;
25        while (arr[j] <= arr[i]) j--;
26
27        (arr[i], arr[j]) = (arr[j], arr[i]);
28        Array.Reverse(arr, i + 1, arr.Length - (i + 1));
29        return true;
30    }
31}
32
33public class Demo
34{
35    public static void Main()
36    {
37        int[] data = { 1, 2, 3, 4 };
38        int count = 0;
39        foreach (var p in Permutations.Generate(data))
40        {
41            count++;
42            if (count <= 5)
43                Console.WriteLine(string.Join(",", p));
44        }
45        Console.WriteLine($"Total: {count}");
46    }
47}

This approach avoids a giant in-memory result list.

Consume permutations with pruning

Many real problems do not need all permutations. Stop early when a condition is met, or prune branches before full permutation completion.

Example strategy:

1. Evaluate partial candidate cost.
2. Abandon branch if cost already exceeds current best.
3. Continue only promising branches.

Pruning transforms impossible workloads into practical ones.

Use counts and limits in API design

If this logic is exposed through a service or UI tool, enforce limits explicitly:

1. Maximum input length.
2. Maximum permutations processed.
3. Timeout per request.

Fail fast with clear message if requested size is unsafe.

Parallelization does not solve memory design

Parallel generation can speed CPU work, but if each worker still stores large permutation sets, memory failures remain. Parallelism should combine with streaming and bounded queues.

Pattern:

1. Producer generates permutations lazily.
2. Worker pool consumes and scores.
3. Results aggregator stores only best or top-N outcomes.

Bounded memory plus parallel compute is the sustainable model.

Diagnostics and measurement

Before optimization, instrument:

1. Input size.
2. Number of permutations processed.
3. Peak memory.
4. Time per million permutations.

Use these metrics to define practical limits and avoid repeating outages.

Alternative algorithms for specific goals

If your actual goal is not full enumeration, use specialized algorithms:

1. For best route approximation, use heuristic search.
2. For ranking top combinations, use branch-and-bound.
3. For counting only, compute combinatorics directly without generation.

Choosing the right algorithm is often more impactful than low-level memory tuning.

Common Pitfalls

• Storing every permutation in nested lists before processing.
• Accepting large input sizes without guardrails or warning.
• Assuming more RAM will make factorial workloads safe.
• Adding parallel threads while keeping unbounded result accumulation.
• Ignoring pruning opportunities in optimization-style permutation tasks.

Summary

• OutOfMemoryException in permutation code is usually a factorial-growth design issue.
• Avoid materializing full permutation sets for non-trivial input sizes.
• Use lazy iteration with yield return and process items incrementally.
• Add limits, pruning, and observability for production safety.
• Prefer goal-specific algorithms when full permutation enumeration is unnecessary.