c# - 在不创建任何运行的情况下打乱数组

Question

我有一个重复字母数组:

AABCCD

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

ACCABD

无效，因为有两个 C 彼此相邻。

ABCACD

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

这个简单示例的每个有效序列:

ABCADC ABCDAC ACBACD ACBADC ACBDAC ACBDCA ACDABC ACDACB ACDBAC ACDBCA ADCABC ADCBAC BACDAC BCADCA CABCAD CABCDA CABDAC CABDCA CADBAC CADBCA CADCAB CADCBA CBACDA CBADCA CDABCA CDACBA DACBAC DCABCA

我对这个小数组使用了强力方法，但我的实际问题是包含数百个元素的数组。我试过使用带有一些抑制的 Fisher-Yates - 做正常的 Fisher-Yates 然后如果你不喜欢出现的角色，多试 X 次以获得更好的角色。仅在大约 87% 的时间内生成有效序列，而且速度非常慢。想知道是否有更好的方法。显然这对所有数组都是不可能的。只有“AAB”的数组没有有效的顺序，所以我想针对这样的事情失败到“ABA”的最佳可用顺序。

Answer 1

这是一种改进的 Fisher-Yates 方法。正如我提到的，很难在 100% 的时间内生成有效序列，因为您必须通过在序列末尾仅留下 AAA 来检查您是否没有陷入困境。

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

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;
}