如何随机排列没有两个重复项的字符数组？

Question

我在面试中被问到这个问题：

How to shuffle a character array with no two duplicates next to each other?

我想出的算法是：

有 HashMap 个字符，字符对的出现次数。通过这个找到重复元素与唯一元素的数量。
如果重复 > 唯一，则无法形成没有 2 的随机数组彼此相邻的重复元素 (?)
如果唯一 >= 重复，则有 2 个堆栈 - 1 个包含唯一字符和一个包含重复字符的字符。构建以从唯一堆栈中弹出元素的方式生成数组首先，然后从重复堆栈中弹出一个元素。重复

例如：

[a,b,b,c] shuffled array with above algorithm - [a,b,c,b];

[b,b,b,c] unique < duplicate return error

但我很确定我的逻辑过于复杂了。有没有更简单、更简单的方法来做到这一点？

Answer 1

这本质上是一道排序题。它让我想起了 'peak finding' 但反过来，你想要 'create peaks' 独特的物品。

另外(2)的逻辑有点不对。如果我有N个重复的字母，我仍然可以没有与另一个字母的N-2个相似的邻居：

'aaabb' -sort-> 'ababa'

这也说明了查找 'uniques,' 的问题，因为您很可能只有数组中某处重复的字母。

伪：

foreach letter in string{
  if next != self then happy, move to next

  if next == self, 
     loop until spot != self and swap

可能有更好的分而治之方法可以在更短的时间内通过它，但如果没有实际测试我不确定。

Answer 2

[正如评论中指出的那样，有一个测试用例失败了]
所以如果参考我的答案，请注意同样的问题我明白了，但如果您有 'a'->4、'b'->2 和 'c'->1，它似乎不起作用。因为第一步是"abc"，留下'a'->3'b'->1。但是有一个答案："ababaca"。 – user3386109

案例 1：构建基本算法

使用哈希图（键是字符，它的出现是值）来计算出现次数。这将为我们提供桶，如果我们有 "cbaaba" 将提供 3 个桶，其中 'c' 值为 1，'a' 值为 3，'b' 值为 2.
根据出现次数对桶进行排序，其中出现次数最多的元素排在最前面。所以现在我们有

'a' -> 3 , 'b' -> 2 , 'c' -> 1

从最大出现桶中获取元素，将其在map中的计数减1并将其放入结果数组中。根据已排序的出现桶，遵循此以获得后续出现桶。

结果数组将以排序的方式从 3 个桶中各取一个开始。

"abc" 现在我们的桶是 'a'->2 , 'b'-> 1 和 'c'-> 0

接下来我们再次尝试从已排序的桶中获取每个元素（忽略具有 0 个元素的桶）

"abcab" 现在我们的桶状态变为：'a'-> 1，'b'-> 0 和 'c'-> 0

接下来如上所述，我们继续得到我们的结果

=> "abcaba".

情况 2：如果字符串类似于 "aaaabbbcccdd"

我们将有桶

'a'--> 4
'b'--> 3
'c'--> 3
'd'--> 2

这里我们有 b 和 c 的桶，大小相同 。 每当出现这种情况时，我们必须执行 JoinBuckets 的 操作，它将单独加入 'b' 和 'c' bucket 和 'bc' 将被视为单个元素。

现在我们的桶将是

'a'--> 4 'bc'--> 3 'd'--> 2

现在按照案例 1 中的相同方式继续进行，我们尝试构建结果

=>结果 = "abcd"

'a'--> 3 'bc'--> 2 'd'--> 1

=>结果="abcdabcd"

'a'--> 2 'bc'--> 1 'd'--> 0

=>结果="abcdabcdabc"

'a'--> 1 'bc'--> 0 'd'--> 0

=>最终结果="abcdabcdabca"

Answer 3

我将从一个非常简单的算法开始：

public static void shuffleWithoutRepetition(char[] chars, Random rnd) {
  if (tooManySameCharacters(chars))
    throw new IllegalArgumentException("Too many same characters");

  do {
    shuffle(chars, rnd); // See java.util.Collections.shuffle
  } while (containsRepetition(chars));
}

这样，你就有了一些工作代码，当它变得太慢时，你可以稍后优化它。

这个算法洗牌的速度很慢aaaaaaaaaaaaaaabbbbbbbbbbbbbbb，这很糟糕。
它以相同的概率生成每个可能的输出，这很好。

Answer 4

SCALA 代码。复制并粘贴此程序和运行.

def rearrange(xs : List[Char]) : List[Char] ={
xs match {
    case Nil => Nil
    case x :: xs1 => xs1 match {
    case Nil => x :: Nil
    case y :: ys1 =>
         if (x == y)  { 
              (x :: rearrange(ys1)) :+ y 
         }
         else
             x :: y :: rearrange(ys1)
         }
     }
}                                               
rearrange: (xs: List[Char])List[Char]

rearrange("hello".toList)

如何随机排列没有两个重复项的字符数组？

How to shuffle a character array with no two duplicates next to each other?

java

arrays

algorithm

shuffle

duplicates