符合以下条件的 N 长序列对
N-length sequences of pairs following conditions
我有以下水果的二维数组：
fruits = [["apple", "lemon"],["apple", "cucumber"],["carrot", "lemon"],["carrot", "cucumber"],["peach", "cucumber"],["lemon", "melon"],["grape", "cucumber"],["lime", "lemon"],["lime", "cucumber"],["apricot", "lemon"],["apricot", "cucumber"],["avocado", "cucumber"],["banana", "lemon"],["banana", "cucumber"],["blackberry", "lemon"],["blackberry", "cucumber"],["blackberry", "prune"],["blueberry", "lemon"],["blueberry", "melon"],["blueberry", "cucumber"],["cherry", "lemon"],["cherry", "cucumber"],["papaya", "lemon"],["plum", "lemon"],["plum", "cucumber"],["feijoa", "lemon"],["fig", "lemon"],["fig", "cucumber"],["eggplant", "lemon"],["eggplant", "cucumber"],["raspberry", "lemon"],["raspberry", "cucumber"],["cranberry", "lemon"],["cranberry", "cucumber"],["pomelo", "lemon"],["pomelo", "cucumber"],["orange", "lemon"],["orange", "cucumber"],["olive", "cucumber"],["gooseberry", "lemon"],["guava", "lemon"],["guava", "blueberry"],["guava", "cucumber"],["redcurrant", "lemon"],["redcurrant", "cucumber"],["pomergranate", "lemon"],["pomergranate", "cucumber"],["nectarine", "cucumber"],["mulberry", "lemon"],["mulberry", "cucumber"],["dragonfruit", "lemon"],["dragonfruit", "cucumber"],["pear", "lemon"],["cucumber", "lemon"],["cucumber", "blueberry"],["cucumber", "salmonberry"],["cucumber", "melon"],["prune", "lemon"],["prune", "guava"],["prune", "cucumber"],["kiwi", "cucumber"],["mangosteen", "cucumber"],["jujube", "lemon"],["jujube", "cucumber"],["clementine", "lemon"],["clementine", "blueberry"],["clementine", "cucumber"],["tangerine", "lemon"],["tangerine", "cucumber"],["pea", "lemon"],["pea", "cucumber"],["tomato", "cucumber"],["yuzu", "cucumber"]]
任务是根据以下条件找到 N 长度的对序列：
- 第一对和最后一对应包含
"lemon"。
- 第一个和最后一个之间的对不应包含
"lemon"。
- 每个连续的两对应该包含一个公共元素。
- 每个连续的 N-1 对，其中 N 不是 3，不应包含所有这些对中共有的任何元素。
N = 4 的示例：
[["apple","lemon"], ["apple","cucumber"], ["clementine","cucumber"], ["clementine","lemon"]]
[["lime","lemon"], ["lime","cucumber"], ["pomelo","cucumber"], ["pomelo","lemon"]]
[["banana","lemon"], ["banana","cucumber"], ["pomergranate","cucumber"], ["pomergranate","lemon"]]
我为 N = 3 和 4 编写了这段代码，
pairs.permutation(n).select do |ar|
if n == 3
(ar[0] & ar[2]) == ["lemon"] && !ar[1].include?("lemon") && (!(ar[0] & ar[1]).empty? && !(ar[1] & ar[2]).empty?)
elsif n == 4
(ar[0] & ar[3]) == ["lemon"] && !ar[1].include?("lemon") && !ar[2].include?("lemon") && ((ar[0] & ar[1] & ar[2]).empty? && (ar[1] & ar[2] & ar[3]).empty?) && (!(ar[0] & ar[1]).empty? && !(ar[1] & ar[2]).empty? && !(ar[2] & ar[3]).empty?)
end
end
但我觉得这不是最好的方法。是否有任何元编程技巧可以使其对任何 N 长度通用？
以下将执行 n 不受限制的所有规则（未检查 n < 3）。
第一条和第二条规则很简单。第三条和第四条规则的大部分工作由 each_cons 完成，它将获得所需的数组以独立于 n.
pairs.permutation(n).select do |ar|
lemon_bracketed = (ar.first & ar.last).include?('lemon')
no_squeeze = !ar[1..-2].include?('lemon')
consecutive_pair = ar.each_cons(2).map { |x| x }.none { |first, last| (first & last).empty? }
consecutive_n = n == 3 ||
ar.each_cons(n-1)
.map { |x| x }
.all? { |group| group[1..-1].reduce(group[0]) { |combination, additional| combination & additional } }
lemon_bracketed && no_squeeze && consecutive_pair && consecutive_n
end
虽然这有效，但速度很慢。但是性能似乎在 pairs.permutation(n) 部分丢失了，所以这里没有什么可以做的。
是的，您可以对任意 length 参数进行暴力破解：
class FruitCombinations
PAIRS = [["apple", "lemon"],["apple", "cucumber"],["carrot", "lemon"],["carrot", "cucumber"],["peach", "cucumber"],["lemon", "melon"],["grape", "cucumber"],["lime", "lemon"],["lime", "cucumber"],["apricot", "lemon"],["apricot", "cucumber"],["avocado", "cucumber"],["banana", "lemon"],["banana", "cucumber"],["blackberry", "lemon"],["blackberry", "cucumber"],["blackberry", "prune"],["blueberry", "lemon"],["blueberry", "melon"],["blueberry", "cucumber"],["cherry", "lemon"],["cherry", "cucumber"],["papaya", "lemon"],["plum", "lemon"],["plum", "cucumber"],["feijoa", "lemon"],["fig", "lemon"],["fig", "cucumber"],["eggplant", "lemon"],["eggplant", "cucumber"],["raspberry", "lemon"],["raspberry", "cucumber"],["cranberry", "lemon"],["cranberry", "cucumber"],["pomelo", "lemon"],["pomelo", "cucumber"],["orange", "lemon"],["orange", "cucumber"],["olive", "cucumber"],["gooseberry", "lemon"],["guava", "lemon"],["guava", "blueberry"],["guava", "cucumber"],["redcurrant", "lemon"],["redcurrant", "cucumber"],["pomergranate", "lemon"],["pomergranate", "cucumber"],["nectarine", "cucumber"],["mulberry", "lemon"],["mulberry", "cucumber"],["dragonfruit", "lemon"],["dragonfruit", "cucumber"],["pear", "lemon"],["cucumber", "lemon"],["cucumber", "blueberry"],["cucumber", "salmonberry"],["cucumber", "melon"],["prune", "lemon"],["prune", "guava"],["prune", "cucumber"],["kiwi", "cucumber"],["mangosteen", "cucumber"],["jujube", "lemon"],["jujube", "cucumber"],["clementine", "lemon"],["clementine", "blueberry"],["clementine", "cucumber"],["tangerine", "lemon"],["tangerine", "cucumber"],["pea", "lemon"],["pea", "cucumber"],["tomato", "cucumber"],["yuzu", "cucumber"]]
def self.list_valid(length)
PAIRS.permutation(length).select do |pair_permutation|
first = pair_permutation[0]
middle = pair_permutation[1..-2]
last = pair_permutation[-1]
first & last == ['lemon'] &&
middle.none? { |pair| pair.include?('lemon') } &&
!(first & middle[0]).empty? &&
!(middle[-1] & last).empty? &&
middle.each_cons(2).none? { |pair_of_pairs| (pair_of_pairs[0] & pair_of_pairs[-1]).empty? }
end
end
end
请注意，这对于长度 == 4 非常慢，对于更长的长度会更慢。正如有人指出的那样，递归解决方案会更有效率。
这是一个递归解决方案，它直接构造所需的数组，而不是构造一个更大的排列数组，然后删除不满足所有规则的元素。
代码
def combos(n, fruits)
with_lemon, without_lemon = fruits.partition { |a| a.include?("lemon") }
return [] if n < 2 || with_lemon.size < 2 || without_lemon.size < n - 2
with_lemon.each_with_object([]) do |pair, arr|
recurse(n, n-1, with_lemon - [pair], without_lemon, pair, pair, fruits.flatten).
each { |a| arr << ([pair] + a) }
end
end
def recurse(n, n_left, with_lemon, without_lemon, last, in_all_from_1st, in_all_from_2nd)
if n_left == 1
with = with_lemon.select { |pair| (last & pair).any? }
with.select! { |pair| (in_all_from_2nd & pair).empty? } unless n <= 3
with.map { |pair| [pair] }
else
without = without_lemon.select { |pair| (last & pair).any? }
return [] if without.empty?
without.each_with_object([]) do |pair, arr|
if n <= 3 || n_left > 2 || (in_all_from_1st & pair).empty?
recurse(n, n_left-1, with_lemon, without_lemon-[pair],
pair, in_all_from_1st, in_all_from_2nd & pair).
each { |a| arr << ([pair] + a) unless a.empty? }
end
end
end
end
例子
为了使示例更易于管理，我在 OP 给出的示例中选择了 73 对中的 8 对。
fruits = [["tomato", "cucumber"], ["fig", "lemon"], ["tomato", "lemon"],
["cucumber", "fig"], ["fig", "tomato"], ["lemon", "cucumber"],
["pomergranate", "cucumber"], ["lemon", "fig"]]
首先我将定义一个助手。这个方法returns一对[f,n]其中f是水果，n是出现f的二元组的个数，n是所有水果中出现次数最多的。
def max_nbr_appearances(n, fruits)
combos(n, fruits).map do |arr|
arr.map(&:uniq).flatten.group_by(&:itself).
transform_values { |v| v.size }.max_by(&:last)
end.max_by(&:last)
end
n = 2
combos(2, fruits)
#=> [[["fig", "lemon"], ["tomato", "lemon"]],
# [["fig", "lemon"], ["lemon", "cucumber"]],
# [["fig", "lemon"], ["lemon", "fig"]],
# [["tomato", "lemon"], ["fig", "lemon"]],
# [["tomato", "lemon"], ["lemon", "cucumber"]],
# [["tomato", "lemon"], ["lemon", "fig"]],
# [["lemon", "cucumber"], ["fig", "lemon"]],
# [["lemon", "cucumber"], ["tomato", "lemon"]],
# [["lemon", "cucumber"], ["lemon", "fig"]],
# [["lemon", "fig"], ["fig", "lemon"]],
# [["lemon", "fig"], ["tomato", "lemon"]],
# [["lemon", "fig"], ["lemon", "cucumber"]]]
n = 3
combos(n, fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["lemon", "cucumber"]],
## [["fig", "lemon"], ["cucumber", "fig"], ["lemon", "fig"]],
# [["fig", "lemon"], ["fig", "tomato"], ["tomato", "lemon"]],
## [["fig", "lemon"], ["fig", "tomato"], ["lemon", "fig"]],
# [["tomato", "lemon"], ["tomato", "cucumber"], ["lemon", "cucumber"]],
# [["tomato", "lemon"], ["fig", "tomato"], ["fig", "lemon"]],
# [["tomato", "lemon"], ["fig", "tomato"], ["lemon", "fig"]], \
# [["lemon", "cucumber"], ["tomato", "cucumber"], ["tomato", "lemon"]],
# [["lemon", "cucumber"], ["cucumber", "fig"], ["fig", "lemon"]],
# [["lemon", "cucumber"], ["cucumber", "fig"], ["lemon", "fig"]],
## [["lemon", "fig"], ["cucumber", "fig"], ["fig", "lemon"]],
# [["lemon", "fig"], ["cucumber", "fig"], ["lemon", "cucumber"]],
# [["lemon", "fig"], ["fig", "tomato"], ["fig", "lemon"]],
# [["lemon", "fig"], ["fig", "tomato"], ["tomato", "lemon"]]]
开头 ** 以上的行有一个水果出现在所有三个二元组中（总是 "fig"）。这是允许的，因为 n = 3 <= 3.
n = 4
combos(n, fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["tomato", "cucumber"],
# ["tomato", "lemon"]],
# [["fig", "lemon"], ["fig", "tomato"], ["tomato", "cucumber"],
# ["lemon", "cucumber"]],
# [["tomato", "lemon"], ["tomato", "cucumber"], ["cucumber", "fig"],
# ["fig", "lemon"]],
# [["tomato", "lemon"], ["tomato", "cucumber"], ["cucumber", "fig"],
# ["lemon", "fig"]],
# [["tomato", "lemon"], ["fig", "tomato"], ["cucumber", "fig"],
# ["lemon", "cucumber"]],
# [["lemon", "cucumber"], ["tomato", "cucumber"], ["fig", "tomato"],
# ["fig", "lemon"]],
# [["lemon", "cucumber"], ["tomato", "cucumber"], ["fig", "tomato"],
# ["lemon", "fig"]],
# [["lemon", "cucumber"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "lemon"]],
# [["lemon", "fig"], ["cucumber", "fig"], ["tomato", "cucumber"],
# ["tomato", "lemon"]],
# [["lemon", "fig"], ["fig", "tomato"], ["tomato", "cucumber"],
# ["lemon", "cucumber"]]]
combos(n, fruits).size
#=> 10
max_nbr_appearances(n, fruits)
#=> ["fig", 2]
最后的计算表明"fig"在一个排列中（至少）出现了两次，没有一个水果（包括"fig"）在一个排列中出现了两次以上。 （出现次数最多的并列很常见，我只展示了一个。）所以满足最后一个条件。
n = 5
combos(n, fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "cucumber"], ["tomato", "lemon"]],
# [["fig", "lemon"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "cucumber"], ["lemon", "cucumber"]],
# ...
# [["lemon", "fig"], ["fig", "tomato"], ["cucumber", "fig"],
# ["pomergranate", "cucumber"], ["lemon", "cucumber"]]]
combos(n,fruits).size
#=> 36
max_nbr_appearances(n, fruits)
#=> ["fig", 3]
n = 6
combos(n,fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "cucumber"], ["pomergranate", "cucumber"], ["lemon", "cucumber"]],
# [["fig", "lemon"], ["fig", "tomato"], ["tomato", "cucumber"],
# ["cucumber", "fig"], ["pomergranate", "cucumber"], ["lemon", "cucumber"]],
# ...
# [["lemon", "fig"], ["fig", "tomato"], ["cucumber", "fig"],
# ["pomergranate", "cucumber"], ["tomato", "cucumber"], ["lemon", "cucumber"]]]
combos(n,fruits).size
#=> 28
max_nbr_appearances(n, fruits)
#=> ["cucumber", 4]
n = 7
combos(7,fruits)
#=> []
对于题中给出的fruits，对于fruits.size #=> 73，得到如下结果。
require 'time'
def ops_fruits(n, fruits)
t = Time.now
puts "\ncombos(#{n}, fruits).size = %d, elapsed seconds = %d" %
[combos(n, fruits).size, Time.now - t]
puts "max_nbr_appearances(#{n}, fruits) = #{max_nbr_appearances(n, fruits)}"
end
ops_fruits(3, fruits)
combos(3, fruits).size = 64, elapsed seconds = 0
max_nbr_appearances(3, fruits) = ["apple", 2]
ops_fruits(4, fruits)
combos(4, fruits).size = 736, elapsed seconds = 0
max_nbr_appearances(4, fruits) = ["apple", 2]
ops_fruits(5, fruits)
combos(5, fruits).size = 27822, elapsed seconds = 1
max_nbr_appearances(5, fruits) = ["cucumber", 3]
ops_fruits(6, fruits)
combos(6, fruits).size = 952504, elapsed seconds = 60
max_nbr_appearances(6, fruits) = ["cucumber", 4]
摘要中：
数据结构是一个图 - 每个水果都是一个顶点，数组中的对是它们之间的边。
要解决这个问题，请执行深度优先搜索。
First and last pairs should contain "lemon".
Pairs between first and last shouldn't contain "lemon".
- DFS 应植根于
"lemon" 节点（级别 0）。
- DFS 不应下降超过
N 级。
- DFS 应该再次访问
"lemon" 节点，除非它处于级别 N。
Each consecutive two pairs should contain a common element.
- 这是图形数据结构的隐式。
Each consecutive N-1 pairs, where N is not 3, shouldn't contain any element common in all of these pairs.
- 在每个顶点（水果）上维护一个标志，表明该顶点是否已被访问 - 如果没有，则 DFS 可以遍历它的边并将其标记为已访问（并且一旦您回溯以找到其他路径，则将其标记为未访问，以便这些路径可以访问它。
我有以下水果的二维数组：
fruits = [["apple", "lemon"],["apple", "cucumber"],["carrot", "lemon"],["carrot", "cucumber"],["peach", "cucumber"],["lemon", "melon"],["grape", "cucumber"],["lime", "lemon"],["lime", "cucumber"],["apricot", "lemon"],["apricot", "cucumber"],["avocado", "cucumber"],["banana", "lemon"],["banana", "cucumber"],["blackberry", "lemon"],["blackberry", "cucumber"],["blackberry", "prune"],["blueberry", "lemon"],["blueberry", "melon"],["blueberry", "cucumber"],["cherry", "lemon"],["cherry", "cucumber"],["papaya", "lemon"],["plum", "lemon"],["plum", "cucumber"],["feijoa", "lemon"],["fig", "lemon"],["fig", "cucumber"],["eggplant", "lemon"],["eggplant", "cucumber"],["raspberry", "lemon"],["raspberry", "cucumber"],["cranberry", "lemon"],["cranberry", "cucumber"],["pomelo", "lemon"],["pomelo", "cucumber"],["orange", "lemon"],["orange", "cucumber"],["olive", "cucumber"],["gooseberry", "lemon"],["guava", "lemon"],["guava", "blueberry"],["guava", "cucumber"],["redcurrant", "lemon"],["redcurrant", "cucumber"],["pomergranate", "lemon"],["pomergranate", "cucumber"],["nectarine", "cucumber"],["mulberry", "lemon"],["mulberry", "cucumber"],["dragonfruit", "lemon"],["dragonfruit", "cucumber"],["pear", "lemon"],["cucumber", "lemon"],["cucumber", "blueberry"],["cucumber", "salmonberry"],["cucumber", "melon"],["prune", "lemon"],["prune", "guava"],["prune", "cucumber"],["kiwi", "cucumber"],["mangosteen", "cucumber"],["jujube", "lemon"],["jujube", "cucumber"],["clementine", "lemon"],["clementine", "blueberry"],["clementine", "cucumber"],["tangerine", "lemon"],["tangerine", "cucumber"],["pea", "lemon"],["pea", "cucumber"],["tomato", "cucumber"],["yuzu", "cucumber"]]
任务是根据以下条件找到 N 长度的对序列：
- 第一对和最后一对应包含
"lemon"。 - 第一个和最后一个之间的对不应包含
"lemon"。 - 每个连续的两对应该包含一个公共元素。
- 每个连续的 N-1 对，其中 N 不是 3，不应包含所有这些对中共有的任何元素。
N = 4 的示例：
[["apple","lemon"], ["apple","cucumber"], ["clementine","cucumber"], ["clementine","lemon"]]
[["lime","lemon"], ["lime","cucumber"], ["pomelo","cucumber"], ["pomelo","lemon"]]
[["banana","lemon"], ["banana","cucumber"], ["pomergranate","cucumber"], ["pomergranate","lemon"]]
我为 N = 3 和 4 编写了这段代码，
pairs.permutation(n).select do |ar|
if n == 3
(ar[0] & ar[2]) == ["lemon"] && !ar[1].include?("lemon") && (!(ar[0] & ar[1]).empty? && !(ar[1] & ar[2]).empty?)
elsif n == 4
(ar[0] & ar[3]) == ["lemon"] && !ar[1].include?("lemon") && !ar[2].include?("lemon") && ((ar[0] & ar[1] & ar[2]).empty? && (ar[1] & ar[2] & ar[3]).empty?) && (!(ar[0] & ar[1]).empty? && !(ar[1] & ar[2]).empty? && !(ar[2] & ar[3]).empty?)
end
end
但我觉得这不是最好的方法。是否有任何元编程技巧可以使其对任何 N 长度通用？
以下将执行 n 不受限制的所有规则（未检查 n < 3）。
第一条和第二条规则很简单。第三条和第四条规则的大部分工作由 each_cons 完成，它将获得所需的数组以独立于 n.
pairs.permutation(n).select do |ar|
lemon_bracketed = (ar.first & ar.last).include?('lemon')
no_squeeze = !ar[1..-2].include?('lemon')
consecutive_pair = ar.each_cons(2).map { |x| x }.none { |first, last| (first & last).empty? }
consecutive_n = n == 3 ||
ar.each_cons(n-1)
.map { |x| x }
.all? { |group| group[1..-1].reduce(group[0]) { |combination, additional| combination & additional } }
lemon_bracketed && no_squeeze && consecutive_pair && consecutive_n
end
虽然这有效，但速度很慢。但是性能似乎在 pairs.permutation(n) 部分丢失了，所以这里没有什么可以做的。
是的，您可以对任意 length 参数进行暴力破解：
class FruitCombinations
PAIRS = [["apple", "lemon"],["apple", "cucumber"],["carrot", "lemon"],["carrot", "cucumber"],["peach", "cucumber"],["lemon", "melon"],["grape", "cucumber"],["lime", "lemon"],["lime", "cucumber"],["apricot", "lemon"],["apricot", "cucumber"],["avocado", "cucumber"],["banana", "lemon"],["banana", "cucumber"],["blackberry", "lemon"],["blackberry", "cucumber"],["blackberry", "prune"],["blueberry", "lemon"],["blueberry", "melon"],["blueberry", "cucumber"],["cherry", "lemon"],["cherry", "cucumber"],["papaya", "lemon"],["plum", "lemon"],["plum", "cucumber"],["feijoa", "lemon"],["fig", "lemon"],["fig", "cucumber"],["eggplant", "lemon"],["eggplant", "cucumber"],["raspberry", "lemon"],["raspberry", "cucumber"],["cranberry", "lemon"],["cranberry", "cucumber"],["pomelo", "lemon"],["pomelo", "cucumber"],["orange", "lemon"],["orange", "cucumber"],["olive", "cucumber"],["gooseberry", "lemon"],["guava", "lemon"],["guava", "blueberry"],["guava", "cucumber"],["redcurrant", "lemon"],["redcurrant", "cucumber"],["pomergranate", "lemon"],["pomergranate", "cucumber"],["nectarine", "cucumber"],["mulberry", "lemon"],["mulberry", "cucumber"],["dragonfruit", "lemon"],["dragonfruit", "cucumber"],["pear", "lemon"],["cucumber", "lemon"],["cucumber", "blueberry"],["cucumber", "salmonberry"],["cucumber", "melon"],["prune", "lemon"],["prune", "guava"],["prune", "cucumber"],["kiwi", "cucumber"],["mangosteen", "cucumber"],["jujube", "lemon"],["jujube", "cucumber"],["clementine", "lemon"],["clementine", "blueberry"],["clementine", "cucumber"],["tangerine", "lemon"],["tangerine", "cucumber"],["pea", "lemon"],["pea", "cucumber"],["tomato", "cucumber"],["yuzu", "cucumber"]]
def self.list_valid(length)
PAIRS.permutation(length).select do |pair_permutation|
first = pair_permutation[0]
middle = pair_permutation[1..-2]
last = pair_permutation[-1]
first & last == ['lemon'] &&
middle.none? { |pair| pair.include?('lemon') } &&
!(first & middle[0]).empty? &&
!(middle[-1] & last).empty? &&
middle.each_cons(2).none? { |pair_of_pairs| (pair_of_pairs[0] & pair_of_pairs[-1]).empty? }
end
end
end
请注意，这对于长度 == 4 非常慢，对于更长的长度会更慢。正如有人指出的那样，递归解决方案会更有效率。
这是一个递归解决方案，它直接构造所需的数组，而不是构造一个更大的排列数组，然后删除不满足所有规则的元素。
代码
def combos(n, fruits)
with_lemon, without_lemon = fruits.partition { |a| a.include?("lemon") }
return [] if n < 2 || with_lemon.size < 2 || without_lemon.size < n - 2
with_lemon.each_with_object([]) do |pair, arr|
recurse(n, n-1, with_lemon - [pair], without_lemon, pair, pair, fruits.flatten).
each { |a| arr << ([pair] + a) }
end
end
def recurse(n, n_left, with_lemon, without_lemon, last, in_all_from_1st, in_all_from_2nd)
if n_left == 1
with = with_lemon.select { |pair| (last & pair).any? }
with.select! { |pair| (in_all_from_2nd & pair).empty? } unless n <= 3
with.map { |pair| [pair] }
else
without = without_lemon.select { |pair| (last & pair).any? }
return [] if without.empty?
without.each_with_object([]) do |pair, arr|
if n <= 3 || n_left > 2 || (in_all_from_1st & pair).empty?
recurse(n, n_left-1, with_lemon, without_lemon-[pair],
pair, in_all_from_1st, in_all_from_2nd & pair).
each { |a| arr << ([pair] + a) unless a.empty? }
end
end
end
end
例子
为了使示例更易于管理，我在 OP 给出的示例中选择了 73 对中的 8 对。
fruits = [["tomato", "cucumber"], ["fig", "lemon"], ["tomato", "lemon"],
["cucumber", "fig"], ["fig", "tomato"], ["lemon", "cucumber"],
["pomergranate", "cucumber"], ["lemon", "fig"]]
首先我将定义一个助手。这个方法returns一对[f,n]其中f是水果，n是出现f的二元组的个数，n是所有水果中出现次数最多的。
def max_nbr_appearances(n, fruits)
combos(n, fruits).map do |arr|
arr.map(&:uniq).flatten.group_by(&:itself).
transform_values { |v| v.size }.max_by(&:last)
end.max_by(&:last)
end
n = 2
combos(2, fruits)
#=> [[["fig", "lemon"], ["tomato", "lemon"]],
# [["fig", "lemon"], ["lemon", "cucumber"]],
# [["fig", "lemon"], ["lemon", "fig"]],
# [["tomato", "lemon"], ["fig", "lemon"]],
# [["tomato", "lemon"], ["lemon", "cucumber"]],
# [["tomato", "lemon"], ["lemon", "fig"]],
# [["lemon", "cucumber"], ["fig", "lemon"]],
# [["lemon", "cucumber"], ["tomato", "lemon"]],
# [["lemon", "cucumber"], ["lemon", "fig"]],
# [["lemon", "fig"], ["fig", "lemon"]],
# [["lemon", "fig"], ["tomato", "lemon"]],
# [["lemon", "fig"], ["lemon", "cucumber"]]]
n = 3
combos(n, fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["lemon", "cucumber"]],
## [["fig", "lemon"], ["cucumber", "fig"], ["lemon", "fig"]],
# [["fig", "lemon"], ["fig", "tomato"], ["tomato", "lemon"]],
## [["fig", "lemon"], ["fig", "tomato"], ["lemon", "fig"]],
# [["tomato", "lemon"], ["tomato", "cucumber"], ["lemon", "cucumber"]],
# [["tomato", "lemon"], ["fig", "tomato"], ["fig", "lemon"]],
# [["tomato", "lemon"], ["fig", "tomato"], ["lemon", "fig"]], \
# [["lemon", "cucumber"], ["tomato", "cucumber"], ["tomato", "lemon"]],
# [["lemon", "cucumber"], ["cucumber", "fig"], ["fig", "lemon"]],
# [["lemon", "cucumber"], ["cucumber", "fig"], ["lemon", "fig"]],
## [["lemon", "fig"], ["cucumber", "fig"], ["fig", "lemon"]],
# [["lemon", "fig"], ["cucumber", "fig"], ["lemon", "cucumber"]],
# [["lemon", "fig"], ["fig", "tomato"], ["fig", "lemon"]],
# [["lemon", "fig"], ["fig", "tomato"], ["tomato", "lemon"]]]
开头 ** 以上的行有一个水果出现在所有三个二元组中（总是 "fig"）。这是允许的，因为 n = 3 <= 3.
n = 4
combos(n, fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["tomato", "cucumber"],
# ["tomato", "lemon"]],
# [["fig", "lemon"], ["fig", "tomato"], ["tomato", "cucumber"],
# ["lemon", "cucumber"]],
# [["tomato", "lemon"], ["tomato", "cucumber"], ["cucumber", "fig"],
# ["fig", "lemon"]],
# [["tomato", "lemon"], ["tomato", "cucumber"], ["cucumber", "fig"],
# ["lemon", "fig"]],
# [["tomato", "lemon"], ["fig", "tomato"], ["cucumber", "fig"],
# ["lemon", "cucumber"]],
# [["lemon", "cucumber"], ["tomato", "cucumber"], ["fig", "tomato"],
# ["fig", "lemon"]],
# [["lemon", "cucumber"], ["tomato", "cucumber"], ["fig", "tomato"],
# ["lemon", "fig"]],
# [["lemon", "cucumber"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "lemon"]],
# [["lemon", "fig"], ["cucumber", "fig"], ["tomato", "cucumber"],
# ["tomato", "lemon"]],
# [["lemon", "fig"], ["fig", "tomato"], ["tomato", "cucumber"],
# ["lemon", "cucumber"]]]
combos(n, fruits).size
#=> 10
max_nbr_appearances(n, fruits)
#=> ["fig", 2]
最后的计算表明"fig"在一个排列中（至少）出现了两次，没有一个水果（包括"fig"）在一个排列中出现了两次以上。 （出现次数最多的并列很常见，我只展示了一个。）所以满足最后一个条件。
n = 5
combos(n, fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "cucumber"], ["tomato", "lemon"]],
# [["fig", "lemon"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "cucumber"], ["lemon", "cucumber"]],
# ...
# [["lemon", "fig"], ["fig", "tomato"], ["cucumber", "fig"],
# ["pomergranate", "cucumber"], ["lemon", "cucumber"]]]
combos(n,fruits).size
#=> 36
max_nbr_appearances(n, fruits)
#=> ["fig", 3]
n = 6
combos(n,fruits)
#=> [[["fig", "lemon"], ["cucumber", "fig"], ["fig", "tomato"],
# ["tomato", "cucumber"], ["pomergranate", "cucumber"], ["lemon", "cucumber"]],
# [["fig", "lemon"], ["fig", "tomato"], ["tomato", "cucumber"],
# ["cucumber", "fig"], ["pomergranate", "cucumber"], ["lemon", "cucumber"]],
# ...
# [["lemon", "fig"], ["fig", "tomato"], ["cucumber", "fig"],
# ["pomergranate", "cucumber"], ["tomato", "cucumber"], ["lemon", "cucumber"]]]
combos(n,fruits).size
#=> 28
max_nbr_appearances(n, fruits)
#=> ["cucumber", 4]
n = 7
combos(7,fruits)
#=> []
对于题中给出的fruits，对于fruits.size #=> 73，得到如下结果。
require 'time'
def ops_fruits(n, fruits)
t = Time.now
puts "\ncombos(#{n}, fruits).size = %d, elapsed seconds = %d" %
[combos(n, fruits).size, Time.now - t]
puts "max_nbr_appearances(#{n}, fruits) = #{max_nbr_appearances(n, fruits)}"
end
ops_fruits(3, fruits)
combos(3, fruits).size = 64, elapsed seconds = 0
max_nbr_appearances(3, fruits) = ["apple", 2]
ops_fruits(4, fruits)
combos(4, fruits).size = 736, elapsed seconds = 0
max_nbr_appearances(4, fruits) = ["apple", 2]
ops_fruits(5, fruits)
combos(5, fruits).size = 27822, elapsed seconds = 1
max_nbr_appearances(5, fruits) = ["cucumber", 3]
ops_fruits(6, fruits)
combos(6, fruits).size = 952504, elapsed seconds = 60
max_nbr_appearances(6, fruits) = ["cucumber", 4]
摘要中：
数据结构是一个图 - 每个水果都是一个顶点，数组中的对是它们之间的边。
要解决这个问题，请执行深度优先搜索。
First and last pairs should contain "lemon".
Pairs between first and last shouldn't contain "lemon".
- DFS 应植根于
"lemon"节点（级别 0）。 - DFS 不应下降超过
N级。 - DFS 应该再次访问
"lemon"节点，除非它处于级别N。
Each consecutive two pairs should contain a common element.
- 这是图形数据结构的隐式。
Each consecutive N-1 pairs, where N is not 3, shouldn't contain any element common in all of these pairs.
- 在每个顶点（水果）上维护一个标志，表明该顶点是否已被访问 - 如果没有，则 DFS 可以遍历它的边并将其标记为已访问（并且一旦您回溯以找到其他路径，则将其标记为未访问，以便这些路径可以访问它。