Introduction

Ruby's permutation and repeated_permutation methods are expensive because they generate enormous output sets. The right way to analyze them is by counting how many sequences they must produce, then multiplying by the work required to build each yielded permutation.

permutation Complexity

If you call array.permutation(r), Ruby generates ordered selections of length r without reuse. The number of results is:

P(n, r) = n! / (n - r)!

where n is the array length.

If each yielded permutation contains r elements, then the overall time is proportional to the number of permutations times the cost to materialize each one. That gives a practical complexity of:

O(P(n, r) * r)

For the common full-length case where r = n, this becomes:

O(n! * n)

That is sometimes shortened informally to factorial time, but the extra * n matters if you care about the cost of constructing or copying each output array.

repeated_permutation Complexity

array.repeated_permutation(r) allows reuse of elements, so the number of outputs is:

n^r

Each yielded result still contains r elements, so the practical complexity is:

O(n^r * r)

That grows extremely fast even for modest n and r.

A Small Ruby Example

The methods themselves are easy to call:

1items = [1, 2, 3]
2
3items.permutation(2) do |perm|
4  p perm
5end
6
7items.repeated_permutation(2) do |perm|
8  p perm
9end

For permutation(2) on three items, Ruby yields 3 * 2 = 6 results. For repeated_permutation(2), it yields 3^2 = 9 results.

That simple example already shows why repeated permutations can explode quickly.

Why the Output Size Dominates

There is no way to generate all permutations faster than the size of the output itself. If your code asks for millions of permutations, the runtime must at least visit millions of results.

That means the complexity is output-bound. Ruby's internal implementation details matter for constant factors, but they do not change the fundamental combinatorial growth.

This is also why the methods feel fine on tiny arrays and then become unusable suddenly. The growth is not linear or quadratic. It is factorial or exponential depending on which method you call.

Memory Use Depends on How You Consume the Results

If you iterate with a block, Ruby can yield one permutation at a time:

1count = 0
2[1, 2, 3, 4].permutation(3) do |_perm|
3  count += 1
4end
5
6puts count

That avoids storing every result at once. But if you convert the enumerator to an array, memory usage explodes along with the output count:

all = [1, 2, 3, 4].permutation(3).to_a
puts all.length

So the time cost is inherent, while the memory cost depends partly on whether you stream the outputs or collect them all.

Practical Guidance

Use these methods only when the input size is small enough that the output count is acceptable. If you merely need to count combinations or test whether some arrangement exists, there is often a better algorithm than enumerating everything.

That is especially true for repeated_permutation, where n^r grows quickly even when r is moderately large.

Common Pitfalls

• Saying the complexity is just O(n!) without accounting for permutation length and output construction cost.
• Forgetting that permutation(r) is smaller than full-length permutation(n).
• Treating repeated_permutation(r) like a minor variation when its output count is n^r.
• Converting the enumerator to an array and then being surprised by memory usage.
• Using permutation generation when the real problem could be solved without enumerating every ordering.

Summary

• 'permutation(r) produces n! / (n - r)! outputs, so the practical time cost is O(P(n, r) * r).'
• Full-length permutations therefore cost about O(n! * n).
• 'repeated_permutation(r) produces n^r outputs, giving O(n^r * r) time.'
• The output size dominates both methods, so combinatorial growth is the real problem.
• Stream permutations with a block when possible instead of collecting them all in memory.