打乱数组而不创建任何运行

本文关键字：创建 任何 运行 数组 | 更新日期: 2024-08-01 21:19:29

我有一个重复字母数组：

AABCCD

我想把它们按伪随机顺序排列。很简单，只需使用Fisher Yates=>完成即可。然而，输出有一个限制——我不想运行任何相同的字母。在同一个字符再次出现之前，我希望至少出现另外两个字符。例如：

ACCABD

无效，因为存在两个彼此相邻的C。

ABCACD-

也是无效的，因为有两个相邻的C（CAC），它们之间只有一个其他字符（A），我需要至少两个其他字符。

这个简单例子的每个有效序列：

ABCADCADCABCCADCAB CADCBA CBACDA CBADCA CDABCA CDACBA DACBAC DCABCA

我对这个小数组使用了蛮力方法，但我的实际问题是有数百个元素的数组。我试过用一些压制性的费雪-耶茨——做正常的费雪·耶茨，然后如果你不喜欢出现的角色，再尝试X次，得到更好的角色。仅在大约87%的时间内生成有效序列，并且速度非常慢。想知道是否有更好的方法。显然，这不可能适用于所有数组。一个只有"AAB"的数组没有有效的顺序，所以我想为类似的事情向下搜索"ABA"的最佳可用顺序。

打乱数组而不创建任何运行

这里是一个经过修改的Fisher-Yates方法。正如我所提到的，100%生成有效序列是非常困难的，因为你必须检查你没有在序列的末尾只留下AAA来困住自己。

可以创建一个递归CanBeSorted方法，该方法告诉序列是否可以根据您的规则进行排序。这将是完整解决方案的基础，但这个函数应该是一个起点，它返回一个指示成功或失败的布尔值。

public static bool Shuffle(char[] array) 
{
    var random = new Random();
    var groups = array.ToDictionary(e => e, e => array.Count(v => v == e));
    char last = ''0';
    char lastButOne = ''0';
    for (int i = array.Length; i > 1; i--)
    {
        var candidates = groups.Keys.Where(c => groups[c] > 0)
            .Except(new[] { last, lastButOne }).ToList();
        if (!candidates.Any())
            return false;
        var @char = candidates[random.Next(candidates.Count)];
        var j = Array.IndexOf(array.Take(i).ToArray(), @char);
        // Swap.
        var tmp = array[j];
        array[j] = array[i - 1];
        array[i - 1] = tmp;
        lastButOne = last;
        last = @char;
        groups[@char] = groups[@char] - 1;
    }
    return true;
}

维护一个链接列表，该列表将跟踪字母及其在结果中的位置。

获得随机数后，从输入中选择相应的字符（与Fisher Yates相同），但现在在列表中搜索是否已经发生。

如果没有，请在结果中插入字母，并在链接列表中插入字母及其在结果中的位置。

如果是，请检查它在结果中的位置（当您在结果中写入该字母时，您已将其存储在链接列表中）。现在将此位置与当前插入位置进行比较，如果mod（currentlocation-previouslocation）为3或更大，则可以在结果中插入该字母，否则不插入，如果不再次选择随机数。

相关文章：