如何使用Linq生成元素为1~n、长度为n*n的所有数组集合

首先明确需求：给定整数n，生成包含n^(n²)个元素的List<int[]>，每个元素是长度为n*n的数组，数组的每个元素取值范围是1到n（并非传统意义上的“排列”，而是所有可能的元素组合，允许重复）。

核心思路 #

本质是构建k层笛卡尔积，其中k = n*n，每一层的可选元素都是1~n。通过动态循环或递归的方式，避免硬编码多层SelectMany。

迭代实现（LINQ） #

using System;
using System.Collections.Generic;
using System.Linq;

public static class ArrayGenerator
{
    public static List<int[]> GenerateAllArrays(int n)
    {
        int targetLength = n * n;
        // 初始集合：包含一个空数组
        IEnumerable<int[]> current = new[] { Array.Empty<int>() };
        
        for (int i = 0; i < targetLength; i++)
        {
            // 每一层都将现有数组与1~n的元素拼接
            current = current.SelectMany(arr => 
                Enumerable.Range(1, n).Select(num => arr.Concat(new[] { num }).ToArray())
            );
        }
        
        return current.ToList();
    }
}

递归实现 #

如果更偏好递归风格，可以用以下方式：

public static class ArrayGenerator
{
    public static List<int[]> GenerateAllArraysRecursive(int n)
    {
        int targetLength = n * n;
        return GenerateRecursive(targetLength, n).ToList();
    }

    private static IEnumerable<int[]> GenerateRecursive(int remainingLength, int n)
    {
        if (remainingLength == 0)
        {
            yield return Array.Empty<int>();
            yield break;
        }

        // 递归生成剩余长度的数组，再逐个拼接当前层的元素
        foreach (var partialArr in GenerateRecursive(remainingLength - 1, n))
        {
            foreach (int num in Enumerable.Range(1, n))
            {
                yield return partialArr.Concat(new[] { num }).ToArray();
            }
        }
    }
}

注意事项 #

• 当n增大时，结果集的规模会呈指数级爆炸：比如n=3时结果数为3^9=19683，n=4时达到4^16=4294967296。此时建议直接使用IEnumerable<int[]>延迟加载，避免调用ToList()一次性占用大量内存。
• 代码中使用Concat会创建新数组，若对性能有极高要求，可以预先分配数组空间并填充，减少内存分配开销。

内容的提问来源于stack exchange，提问作者DreamingOfSleep