随机播放列表算法

Question

随机播放列表算法

c#algorithmplaylistsmart-playlist

13

我需要创建一个数字列表，列表中的数字是从给定范围（例如从x到y）内以随机顺序出现的，并且每种排列方式具有相等的概率。

我需要在C#中编写的音乐播放器中使用此功能来创建随机播放列表。

有什么想法吗？

谢谢。

编辑： 我不打算改变原始列表，只需从范围内以随机顺序选择随机索引，以便每种排列方式具有相同的概率。

这是我已经编写的内容：

    public static IEnumerable<int> RandomIndexes(int count)
    {
        if (count > 0)
        {
            int[] indexes = new int[count];
            int indexesCountMinus1 = count - 1;

            for (int i = 0; i < count; i++)
            {
                indexes[i] = i;
            }

            Random random = new Random();

            while (indexesCountMinus1 > 0)
            {
                int currIndex = random.Next(0, indexesCountMinus1 + 1);
                yield return indexes[currIndex];

                indexes[currIndex] = indexes[indexesCountMinus1];
                indexesCountMinus1--;
            }

            yield return indexes[0];
        }
    }

它可以工作，但唯一的问题是我需要在内存中分配一个大小为count的数组。我正在寻找不需要内存分配的东西。

谢谢。

- Alon Gubkin

参见：https://dev59.com/l3M_5IYBdhLWcg3wp06l - Ryan Emerle

5

不能修改原始列表或分配额外的内存，就无法跟踪重复项。这会导致用户体验不佳。 - Mark Ransom

完全同意Mark Ransom的观点。 - Peter Perháč

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mladen Prajdic · Answer 1

你可以使用在SQL Server中常用的一个技巧来随机排序集合，就像使用GUID一样。这样可以保证数值的分布是均匀随机的。

private IEnumerable<int> RandomIndexes(int startIndexInclusive, int endIndexInclusive)
{
    if (endIndexInclusive < startIndexInclusive)
        throw new Exception("endIndex must be equal or higher than startIndex");

    List<int> originalList = new List<int>(endIndexInclusive - startIndexInclusive);
    for (int i = startIndexInclusive; i <= endIndexInclusive; i++)
        originalList.Add(i);

    return from i in originalList
           orderby Guid.NewGuid()
           select i;
}

- Ian Henry · Answer 2

你需要分配一些内存，但不必太多。你可以通过使用布尔数组而不是整数来减少内存占用（我不确定减少的程度，因为我对C#的内部结构不是很了解）。最理想的情况是，这将只使用（count / 8）字节的内存，这并不太糟糕（但我怀疑C#实际上并没有将布尔值表示为单个位）。

    public static IEnumerable<int> RandomIndexes(int count) {
        Random rand = new Random();
        bool[] used = new bool[count];

        int i;
        for (int counter = 0; counter < count; counter++) {
            while (used[i = rand.Next(count)]); //i = some random unused value
            used[i] = true;
            yield return i;
        }
    }

希望这有所帮助！