Как реализовать ограниченную перетасовку последовательности ⇐ C#

[Anonymous]

У меня была потребность в моделировании вывода многопоточного сценария, где несколько потоков обрабатывают параллельно упорядоченную последовательность. Вывод больше не упорядочен, но также не полностью перетасовывается. Я думал, что внедрение такого перетасовки должно быть тривиальным, и не займет более 10-20 минут. Но это оказалось намного сложнее, чем я. Так что теперь после многих часов борьбы с проблемой и уточнения требований на этом пути мне удалось создать сложную реализацию с не оптимальным статистическим поведением. Давайте начнем с указания требований: < /p>

[*] Метод должен вернуть отложенную ienumerable < /code>, чтобы последовательности бесконечной длины можно было перетасоваться. Например, последовательность из 100 элементов, перетасованных с помощью maxDisplacement = 2 должна иметь ~ 20 элементов, перемещенных на -2, ~ 20 на -1, ~ 20, не вытесненные, ~ 20 на +1 и ~ 20 на +2.
перетасование должно быть случайным. Различные призывы метода должны обычно возвращать по -разному перетасованной последовательность. < /Li>
< /ol>
Пример ввода и вывода. A sequence of 20 elements is shuffled with maxDisplacement = 5.

Input: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

Output: 0, 3, 2, 5, 7, 1, 4, 6, 8, 12, 9, 11, 13, 10, 15, 16, 19, 14, 17, 18, < /p>
< /blockquote>
Ниже моя лучшая попытка пока: < /p>

Код: Выделить всё

public static IEnumerable ConstrainedShuffle(
this IEnumerable source, Random random, int maxDisplacement)
{
if (maxDisplacement < 1)
throw new ArgumentOutOfRangeException(nameof(maxDisplacement));
random = random ?? new Random();
var buffer = new SortedDictionary();

IEnumerable EnumerateInternal()
{
int index = -1;
int bufferMaxIndex = -1;
foreach (var item in source)
{
bufferMaxIndex++;
buffer.Add(bufferMaxIndex, item);
if (bufferMaxIndex >= maxDisplacement)
{
// Start yielding when buffer has maxDisplacement + 1 elements
index++;
yield return (index, bufferMaxIndex);
}
}
while (buffer.Count > 0) // Yield what is left in the buffer
{
while (!buffer.ContainsKey(bufferMaxIndex)) bufferMaxIndex--;
index++;
yield return (index, bufferMaxIndex);
}
}

foreach (var (index, bufferMaxIndex) in EnumerateInternal())
{
int bufferMinIndex = buffer.First().Key;
int selectedKey;
if (index - bufferMinIndex >= maxDisplacement)
{
// Forced picking of the earliest element
selectedKey = bufferMinIndex;
}
else
{
// Pick an element randomly (favoring earlier elements)
int bufferRange = bufferMaxIndex - bufferMinIndex + 1;
while (true)
{
var biasedRandom = Math.Pow(random.NextDouble(), 2.0);
var randomIndex = (int)(biasedRandom * bufferRange);
selectedKey = bufferMinIndex + randomIndex;
if (buffer.ContainsKey(selectedKey)) break;
}
}
yield return buffer[selectedKey];
buffer.Remove(selectedKey);
}
}
< /code>
Эта реализация не выполняет 3 -е требование. Распределение смещений является странной кривой, с пиком максимального положительного смещения (значительно преувеличивается для больших значений максимального размещения 

). Вот распределение последовательности элементов 1 000 000, перетасованных с MaxDisplacement = 10 :
-10: 44,188
-9: 44,199
-8: 43,701
-7: 43,360
-6: 43,134
-5: 43,112
-4: 42,870
-3: 43,628
-2: 44,170
-1: 45,479
0: 50,029
+1: 58,611
+2: 67,077
+3: 71,663
+4: 70,175
+5: 62,914
+6: 52,835
+7: 40,974
+8: 30,553
+9: 21,210
+10: 36,118
< /code>

отрицательные /положительные смещения: 437,841 /512,130 < /p>
< /blockquote>
Возможно, что мне не хватает более простого решения этой проблемы. < /p>

Подробнее здесь: https://stackoverflow.com/questions/569 ... a-sequence