获取Ruby数组中最长的前缀

Question

我有一个数组。在每个子数组中，如果两个或多个元素共享一个长度等于或大于8的前缀，那么我想用它们最长的前缀替换这些元素。对于此阵列：

m = [
  ["A", "97455589955", "97455589920", "97455589921"],
  ["B", "2348045101518", "2348090001559"]
]

我希望输出如下：

n = [
  ["A", "974555899"],
  ["B", "2348045101518", "2348090001559"]
]

对于m中的第一个子数组，最长前缀为长度为9的974555899。

974555899-55
974555899-20
974555899-21

对于第二个子阵列，最长的前缀是长度为5的23480，长度小于8。在这种情况下，第二个子阵列保持原样。

23480-45101518
23480-90001559

对于此输入：

m = [
  ["A", "2491250873330", "249111222333", "2491250872214", "2491250872213"],
  ["B", "221709900000"],
  ["C", "6590247968", "6590247969", "6598540040", "65985400217"]
]

输出应如下所示：

[
  ["A", "2491250873330", "249111222333", "249125087221"],
  ["B", "221709900000"],
  ["C", "659024796", "65985400"]
]

对于数组m[0][code>，其四个数字之间没有足够长的前缀，但在m[0][2][code>和m[0][3][code>之间有一个长度为12的前缀。对于数组m[2][code>，在m[2][0][code>和m[2][1][code>之间有长度为9的前缀“659024796”，在m[2][2][code>和m[2][3][code>之间有长度为8的前缀“65985400”。

我构建了以下代码：

m.map{|x, *y|
  [x, y.map{|z| z[0..7]}.uniq].flatten
}

通过我的代码和第一个输入，我得到了这个输出。

[
  ["A", "97455589"],
  ["B", "23480451", "23480900"]
]

我一直在研究如何在不设置固定长度的情况下动态获取公共前缀。

Answer 1

您的任务可以分为两部分：计算最大公共数和修改原始数组。

最大公共数在数组上运行，因此，它应该是数组的一种方法。

计算LCN后，您可以将其长度与限制（即8）进行比较。

class Array
  def lcn
    first.length.times do |index|
      numb = first[0..index]
      return numb unless self[1..-1].all? { |n| n.start_with?(numb) }
    end

    first
  end
end

def task(m, limit = 8)
  m.map { |i,*n| [i, n.lcn.length >= limit ? n.lcn : n].flatten }
end

task(m) # => [["A", "9745558995"], ["B", "2348045101518", "2348090001559"]]

在您的解决方案中，实际上并没有实现lcn查找和过滤输出。

Answer 2

这是一个有趣的问题。以下是我的解决方案：

def lcn(lim, *arr)
  # compute all substrings of lengths >= lim and build a lookup by length
  lookup = lcn_explode(lim, arr)

  # first pass: look for largest common number among all elements
  res, = lcn_filter(arr, lookup) { |size| size == arr.size }

  return res unless res.empty?

  # second pass: look for largest common number among some elements
  res, rem = lcn_filter(arr, lookup) { |size| size > 1 }

  # append remaining candidates with no matches
  res.concat(rem)
end

def lcn_explode(lim, arr)
  memo = Hash.new { |h, k| h[k] = Array.new }

  arr.uniq.each do |n|
    lim.upto([n.size, lim].max) do |i|
      memo[i] << [n[0, i], n]
    end
  end

  memo
end

def lcn_filter(arr, lookup)
  memo = []

  lookup.keys.sort!.reverse_each do |i|
    break if arr.empty?

    matches = Hash.new { |h, k| h[k] = Array.new }
    lookup[i].each do |m, n|
      matches[m] << n if arr.include?(n)
    end

    matches.each_pair do |m, v|
      next unless yield v.size

      memo << m

      # remove elements from input array so they won't be reused
      arr -= v
    end
  end

  return memo, arr
end

你这样使用它：

p lcn(8, "97455589955", "97455589920", "97455589921") => ["974555899"]

或：

m.each do |key, *arr|
  p [key, *lcn(8, *arr)]
end

哪些打印：

["A", "249125087221", "2491250873330", "249111222333"]
["B", "221709900000"]
["C", "659024796", "65985400"]

Answer 3

密码

def doit(arr, min_common_length)
  arr.map do |label, *values|
    [label, values.group_by { |s| s[0, min_common_length] }.
      map { |_,a| a.first[0, nbr_common_digits(a, min_common_length)] }]
  end
end

def nbr_common_digits(a, min_common_length)
  max_digits = a.map(&:size).min
  return max_digits if max_digits == min_common_length + 1
  (min_common_length..max_digits).find { |i|
    a.map { |s| s[i] }.uniq.size > 1 } || max_digits
end

示例

arr = [["A","2491250873330","249111222333","2491250872214","2491250872213"],
       ["B","221709900000"],
       ["C","6590247968","6590247969","6598540040","65985400217"]]

doit(arr, 8)
  #=> [["A", ["249125087", "249111222333"]],
  #    ["B", ["221709900000"]],
  #    ["C", ["659024796", "65985400"]]]

解释说明

让我们首先考虑helper方法，nbr_common_digits。假设

a = ["123467", "12345", "1234789"]
min_common_length = 2

然后，步骤如下。

max_digits = a.map(&:size).min
  #=> 5 (the length of "12345")
max_digits == min_common_length + 1
  #=> 5 == 2 + 1
  #=> false, so do not return max_digits
b = (min_common_length..max_digits).find { |i| a.map { |s| s[i] }.uniq.size > 1 }
  #=> (2..5).find { |i| a.map { |s| s[i] }.uniq.size > 1 }
  #=> 4

此时，我们必须考虑当所有字符串的前5个字符相等时，b将等于nil的可能性。在这种情况下，我们应该返回最大\u位数，这就是为什么我们需要以下内容。

b || max_digits
  #=> 4

在doit中，步骤如下所示。

min_common_length = 8

首先，我们使用可枚举的#group\u by按值的第一个min\u common\u长度数字对值进行分组。

arr.map { |label, *values| [label,
  values.group_by { |s| s[0, min_common_length] }] }
  #=> [["A", {"24912508"=>["2491250873330", "2491250872214", "2491250872213"],
  #           "24911122"=>["249111222333"]}],
  #    ["B", {"22170990"=>["221709900000"]}],
  #    ["C", {"65902479"=>["6590247968", "6590247969"],
  #           "65985400"=>["6598540040", "65985400217"]}]]

第二步是计算最长公共长度，并根据需要替换值。

arr.map do |label, *values| [label,
  values.group_by { |s| s[0, min_common_length] }.
         map { |_,a| a.first[0, nbr_common_digits(a, min_common_length)] }]
end
  #=> [["A", ["249125087", "249111222333"]],
  #    ["B", ["221709900000"]],
  #    ["C", ["659024796", "65985400"]]]

第二个映射块中的第一个块变量（其值等于具有nbr\U common\U长度的字符串--“按分组条件分组”）由下划线（合法的局部变量）表示，表示未在块计算中使用该变量。