ruby 。打乱数组，使相邻的元素不具有相同的值

Question

给出了一个哈希数组(至少 10 个元素):

arr = [{letter: "a", number: "1"}, {letter: "a", number: "3"}, {letter: "b", number: "4"}, {letter: "b", number: "1"}, ..., {letter: "e", number: "2"} ]

任务是打乱数组，使相邻元素不具有相同的“字母”值。

所以，结果应该是这样的:

[{letter: "c", number: "4"}, {letter: "a", number: "1"}, {letter: "e", number: "2"}, {letter: "b", number: "1"}, ..., {letter: "a", number: "3"} ]

最简单的方法是什么？

===更新===

数组中重复字母的数量是精确已知的——它是数组长度的 20%。因此，数组如下所示:

[
{letter: "a", number: "1"}, {letter: "a", number: "3"}, 
{letter: "b", number: "4"}, {letter: "b", number: "1"},
{letter: "c", number: "7"}, {letter: "c", number: "3"},
{letter: "d", number: "6"}, {letter: "d", number: "4"},
{letter: "e", number: "5"}, {letter: "e", number: "2"}
]

或者，它的简化版本:

["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]

或者，例如，有一个包含 15 个元素的简化数组:

["a", "a", "a", "b", "b", "b", "c", "c", "c", "d", "d", "d", "e", "e", "e"]

Answer 1

最简单的方法(没有任何随机):

# Calculate letter frequency
freq = arr.group_by { |h| h[:letter] }.map { |k, v| [k, v.size] }.to_h

# Then check that the most frequent element occurs less that arr.size / 2
center = (arr.size + 1) / 2
if freq.values.max > center
  # Impossible
end

# Sort array by frequency to have most frequent first.
sarr = arr.sort_by { |h| freq[h[:letter]] }.reverse

sarr[0..center-1].zip(sarr[center..-1]).flatten.compact

您的问题是 this question 的特例.参见 my answer详细解释这是如何工作的。

---

我们甚至不需要按字母频率排序。它适用于像“abbcccc”这样的极端情况。我们可以用另一种方式解决它们:

# Works with correct data: most frequent letter occurs <= center times
def f(arr)
  arr = arr.sort
  center = (arr.size + 1) / 2
  arr = arr[0..center-1].zip(arr[center..-1]).flatten.compact
  double = (1..arr.size-1).find { |i| arr[i] == arr[i-1] }
  double ? arr.rotate(double) : arr # fix for the corner cases
end

puts f(%w[a a a a b b c].shuffle).join
# ababaca
puts f(%w[a a b b b b c].shuffle).join
# bcbabab
puts f(%w[a b b c c c c].shuffle).join
# cacbcbc

该算法唯一的非线性部分是arr.sort。但是正如您通过上面的链接看到的，我们甚至不需要排序。我们需要字母计数，这可以在线性时间内找到。因此，我们可以将算法减少到O(n)。

---

The number of repeated letters in the array is precisely known - it's 20% of the array length.

通过这次更新，算法被简化为(因为没有极端情况):

sarr = arr.sort_by { |h| h[:letter] }
center = (arr.size + 1) / 2
sarr[0..center-1].zip(sarr[center..-1]).flatten.compact