-1

我有两个不同长度的数组。我想将它们放入哈希中，尽可能均匀地分布元素。

编辑：对不起，我意识到我没有提供足够的输入。“尽可能均匀”是指以下内容：

array1 总是比 array2 有更多的元素。

array2 元素是字符串。最小的单位是单词。

更新的目标 对于生成的哈希，我希望根据平均字数比（所有元素 array2 到 array1.join(" ").split(" ")）将值分配给键。这样我就可以在不破坏字符串完整性的情况下将数字分配到尽可能接近平均值的字符串。您还可以将结果显示为：

result = {"The older son of a woman" =>[320, 321, 322, 323],...}

我很抱歉造成混乱，我想应用程序的目的让我以某种颠倒的方式想到了这一点..

我可以让下面的示例代码在某些情况下工作，但在某些情况下却不行。

array1.clear
array2.clear

array11 = [336, 337, 338, 339, 340, 342, 344, 345, 346, 347, 348]
array22 = ["New research", "suggests that hoarders have unique patterns", "of brain activity", "when faced with making decisions", "about their possessions."] 

array1 =  [320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 331, 332, 333, 334] 
array2 = ["The older son of a woman", "killed at Sunday's mass shooting", "in Wisconsin said she was shot just", "after completing prayers."] 


def hash_from_arrays(array1, array2)
 hash  =  Hash.new{|h,k| h[k] = [] }
  arr_ratio = arr1_to_arr2_ratio(array2, array1)
  start =  0
  last_arr1_to_arr2 = Float(Float(array2.last.split(" ").length)*Float(arr_ratio)).floor
  array1.each_with_index do | element, index|
    arr1_for_arr2_ratio = Float(Float(array2[0].split(" ").length)*Float(arr_ratio)).floor
    hash[element] = array2[0]
    if arr1_for_arr2_ratio + start == index && array2.length > 1
      array2.shift
      start = index
    end
  end
  return hash
end



def arr1_to_arr2_ratio(array1, array2)
  word_count = 0.0
  array1.each{|string| word_count = word_count + string.split(" ").length}
  result = Float(array2.length) / word_count
  return result
end



 hash_from_arrays(array1, array2)
 => {320=>"The older son of a woman", 321=>"The older son of a woman", 322=>"The older son of a woman", 323=>"The older son of a woman", 324=>"The older son of a woman", 325=>"killed at Sunday's mass shooting", 326=>"killed at Sunday's mass shooting", 327=>"killed at Sunday's mass shooting", 328=>"in Wisconsin said she was shot just", 329=>"in Wisconsin said she was shot just", 331=>"in Wisconsin said she was shot just", 332=>"in Wisconsin said she was shot just", 333=>"after completing prayers.", 334=>"after completing prayers."}

编辑更新了代码，现在它适用于两个数组。我想一般都有效...如果有人可以提出更好的解决方案，那就太好了。

4

2 回答 2

1

0) 问题描述：

我有两组，我想定义它们之间的映射。

首先是一组唯一的字符串，命名为 SS 或“字符串”，其项称为“字符串”。
第一个集合是有限的，它由 NStrings 个项目组成。
第一组中的每个字符串可以由任意数量的单词组成，用 NumWords(string) 表示。
因此，第一组还提供了每个字符串的平均字数的统计属性，用 TargetAVG 表示。

第二个是一组唯一的数字，命名为 KK 或“keys”，其项称为“a key”。
第二组是有限的，它由 NKeys 项组成。
这些数字的确切值无关紧要，它们仅用作唯一标识符。

保证第二组比第一组有更多的条目。

我想在第一组和第二组之间生成映射 MM。
第二组（键）中的每一项都应准确分配第一组（字符串）中的一项。
此映射必须至少使用第一组（字符串）中的每个项目一次。
第一组中的任何一项（字符串）都可以多次使用。
因此，映射还从第一组（字符串）中生成给定项目的多次使用的统计属性，用 NumUses(string) 表示。

我想生成这样的映射，即分配给键的字符串中的单词数产生相同的 TargetAVG 平均值（或尽可能接近），并注释字符串计数为平均值的多次映射使用它的次数。

1) 重述：

问题：

从一组固定的独特物品中选择固定数量的不同价值物品，以最适合目标总价值。要选择的项目数大于项目数，这部分项目必须多次选择。

额外限制：

每个项目必须至少选择一次。

在哪里：

items = SS
target item count = NKeys
item value = NumWords(item) * NumUses(item)
target total value = TargetAVG * NKeys (= 估计整个映射中的单词总数)

2）让我们尝试降低问题的复杂性：

键比字符串多 + 每个字符串必须至少使用一次 + 每个键必须只使用一次。
因此，正确生成的映射将包含一个子集，该子集由映射到不同键的每个字符串组成。
因此，一个 NString 的键已经部分解决了，因为我们知道它们必须与每个字符串一对一地匹配，我们只是不知道顺序。例如，我们知道 70 个键中的大约 30 个必须与 30 个字符串中的每一个进行 1 对 1 配对，但我们不知道哪个键对应哪个字符串。但是，分配的确切顺序从来都不重要，所以我们甚至可以直接映射它们：第一个到第一个，第二个到第二个，……第 30 个到第 30 个。
这正是我们为减少问题所做的。

所以：

-) 我们总是可以减少，因为键比字符串多
-) 并且为此，我们总是会留下一些剩余的键，正是 (NKeys-NStrings)
-) 保证“每个项目必须是至少选择一次”

健全性检查：
部分解决方案已用完 NStrings 个键，我们只剩下 (NKeys-NStrings) 个键。
最终解决方案必须达到等于 TargetAVG 的平均值。
我们已经在键的第一个 NStrings 上使用了所有 NStrings 个字符串。
这意味着我们的部分解决方案保证在内部具有“TargetAVG”的平均值。
我们还剩下一些钥匙。
这意味着其余键的映射也应该具有“TargetAVG”的平均值，或者尽可能接近。
我们已经满足了要求，我们现在可以随时使用任何字符串，甚至为零。

一切听起来都很棒。

3）遗留问题：

问题类型：

选择固定数量的有价值物品以最适合目标总价值。任何项目我都可以选择任意次数。

在哪里：

items = SS
target item count = (NKeys-NStrings)
item value = NumWords(item) * NumUses(item)
target total value = TargetAVG * (NKeys-NStrings) （= 剩余映射中估计的单词总数）

重要的是，我们希望通过使用精确的“X”个选择来获得最接近给定值“S”的总和。
这意味着它不是一般的背包包装问题，而是它的一种子类，一种 改变问题。让我们试试它是否适合：

我们需要以最少使用不同价值的硬币来处理一定数量的现金。
=>
我们需要在一些具有不同字数的字符串之间拆分指定数量的单词，恰好 X 选择。

另外，如果理想是不可能的，我们希望获得“最佳近似”结果。

背包问题被归类为 NP，一般来说，获得精确或最佳可能是困难的或非常耗时的。在谷歌上花了一些时间之后，我还没有找到任何现成的算法可以用精确的 N 选择来解决金钱问题，并且可能这类问题只是以其他名称而闻名，我现在不记得了. 我非常建议您搜索，或询问有关如何分类此类问题的问题。如果有人更精通算法命名法的答案，您甚至可以立即找到可行的解决方案。

其他需要考虑的事情：您的“最佳结果”需求有多严重，实际上，它需要有多接近？相对于字符串的数量会有多少键？字符串的字数会有多少变化？任何额外的条件都可能有助于放下背包并使用一些在这些条件下碰巧是安全的幼稚方法。

例如，如果剩余（NKey-NSstrings）的数量很少，只需启动一个完整的指数搜索，它将检查所有可能性，您肯定会得到最好的结果。

否则，如果您不需要最好的结果并且 (NKeys-NStrings) 很高并且字数相对均匀，那么您可能只需进行简单的贪婪分配，而错误分配的几个项目将使平均值只差一点（几个项目除以高 NKeys-NStrings = 平均值的低分数）。

在其他情况下，或者如果您真的需要最佳匹配，您可能需要进入“动态规划”或“整数线性规划”，以便为类似问题生成近似解。

如果我对此有任何想法，我会添加它们并发表评论，但实际上我怀疑。在我的记忆中，我已经写了所有的东西，只有当我真的再次把鼻子贴在算法书上时，我才能给你更多的指点，遗憾的是我现在几乎没有时间了：）给我一个如果您偶然发现问题的正确分类，请注意！

于 2012-08-12T20:29:10.863 回答
1

我很高兴你有一些解决方案:)

我玩了一点你的 nevest 代码，让我们有：

array1 =  [320, 321, 322, 323, 324]
array2 = ["a a a a a a a a a a a a a a a a", "b"]

irb(main):071:0> pp hash_from_arrays(array1, array2)
{320=>"a a a a a a a a a a a a a a a a",
 321=>"a a a a a a a a a a a a a a a a",
 322=>"a a a a a a a a a a a a a a a a",
 323=>"a a a a a a a a a a a a a a a a",
 324=>"a a a a a a a a a a a a a a a a"}

1）完全不使用“B”可以吗？
2) array2 有 17 个单词，除以 array1 中的 5 个键 = 平均每个键 3.4 个单词。结果每个键平均有 16 个单词，这与 3.4 相差甚远。显然，如果“b”被使用几次，avg 会更接近 3.4。

或者，也许我再次不明白您心中的分布/平均值是什么？

于 2012-08-11T01:11:55.607 回答