如何在 C# 中实现列表的延迟改组？

Question

我正在寻找 c# 中的惰性改组的实现。

我只关心处理前几个元素所花费的时间。我不关心原始列表是否被修改（即删除元素就可以了）。我不在乎迭代器到达列表末尾时处理时间是否变长（当然只要它保持在合理范围内）。

上下文：我有一个很大的列表，我想从中获取相对较少的随机样本。在大多数情况下，我只需要第一个随机元素，但在极少数情况下，我需要列表中的所有元素。

如果可能的话，我想将其实现为扩展方法，就像这样（但没有扩展方法的答案也很好）：

public static class Program
{
    public static IEnumerable<T> lazy_shuffle<T>(this IEnumerable<T> input, Random r)
    {
        //do the magic
        return input;
    }
    static void Main(string[] args)
    {
        var start = DateTime.Now;
        var shuffled = Enumerable.Range(0, 1000000).lazy_shuffle(new Random(123));
        var enumerate = shuffled.GetEnumerator();
        foreach (var i in Enumerable.Range(0, 5))
        {
            enumerate.MoveNext();
            Console.WriteLine(enumerate.Current);
        }
        Console.WriteLine($"time for shuffling 1000000 elements was {(DateTime.Now - start).TotalMilliseconds}ms");
    }
}

注：

input.OrderBy(i => r.Next()) 不够好，因为一旦为列表的每个元素生成一个随机数，它就需要遍历整个列表。
这不是 Lazy Shuffle Algorithms 的副本，因为我的问题对算法的限制不那么严格，而是需要在 c#
这不是 Randomize a List<T> 的重复，因为该问题是关于常规洗牌而不是惰性洗牌的。

更新：

一个 Count 存在。存在对元素的随机访问。它不是严格意义上的可枚举的，而只是一个大的 List 或 Array。我已将问题更新为“列表”而不是“ienumerable”。只有 lazy-shuffler 的输出需要是可枚举的，源可以是一个实际的列表。
选择应该是公平的，即每个元素需要有相同的机会首先被选中。
mutation/modification 没问题
最后我只需要从列表中随机取N个元素，但我事先不知道这N个

Answer 1

由于可以修改原始列表，这里有一个非常简单高效的解决方案，基于this answer:

public static IEnumerable<T> Shuffle<T>(this IList<T> list, Random rng)
{
    for(int i = list.Count - 1; i >= 0; i--)
    {
        int swapIndex = rng.Next(i + 1);
        yield return list[swapIndex];
        list[swapIndex] = list[i];
    }
}

如何在 C# 中实现列表的延迟改组？

How to implement lazy shuffling of Lists in C#?

c#

linq

algorithm

shuffle

lazy-evaluation