主页 / user-224871

Surfin Bird's questions

Martin Hope
Surfin Bird
Asked: 2020-10-20 01:47:35 +0000 UTC
  • 11

如何在不让元素从其原始位置移动超过给定数量 (N) 的情况下对数组进行洗牌？假设 N=1:[1, 2, 3, 4, 5]可以混入[1, 3, 2, 4, 5]or [2, 1, 3, 5, 4]，但不能混入[5, 2, 1, 3, 4].

有没有任何算法？唉，我什么都google不了，我的实现也不是很统一。

但是，以防万一：

/// <summary>
/// Возвращает перемешанный заданным образом массив размером size с элементами от 0
/// до size−1. В дальнейшем этот массив будет использован как список новых позиций.
/// </summary>
/// <param name="size">Число элементов</param>
/// <param name="limit">Максимальное смещение</param>
/// <returns>Перемешанный список индексов</returns>
private int[] Shuffle(int size, int limit) {
    var buffer = new int[size];
    for (var i = 0; i < buffer.Length; i++) {
        buffer[i] = i;
    }

    for (var i = buffer.Length - 1; i >= 0; i--) {
        // Узнаём оригинальную позицию элемента
        var t = buffer[i];

        // Границы для поиска относительно оригинальной позиции
        var a = Math.Max(t - limit, 0);
        var b = Math.Min(t + limit, buffer.Length - 1);

        // Выбираем кандидата на обмен
        var n = _randomInstance.Next(a, b + 1);

        // Самого на себя не меняем
        if (n != i) {
            // Возможные границы обмена для найденного элемента
            var ai = Math.Max(i - limit, 0);
            var bi = Math.Min(i + limit, buffer.Length - 1);

            // Узнаём оригинальную позицию элемента
            var v = buffer[n];

            // Если оригинальная позиция найденного вписывается в границы
            // вокруг i, можно заменить
            if (v >= ai && v <= bi) {
                buffer[i] = buffer[n];
                buffer[n] = t;
            }
        }
    }

    return buffer;
}
алгоритм