Ruby中的回溯和组合电子学问题

Question

所以我一直在努力解决这个问题，但有点拘泥于使用回溯来实现它，我真的很想了解我在这里做错了什么。我怀疑我的问题与方法中通过引用传递的数组有关，但我似乎无法理解。任何帮助都将不胜感激。这是在一次采访中被问到的，我正试图自己解决这个问题。

问题是：

卡片有一套和重复的时间。给定一个卡片列表和输出大小，返回一个带有的卡片列表

(所有相同的字母或所有不同的字母(&(所有相同的长度或所有不同的字母长度(。

exaple1:
input: ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
output: ['X', 'YY', 'ZZZ']
-------------
example2:
input: ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX'], 3
output: ['Y', 'Z', 'X']
-------------
example3:
input: ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
output: ['X', 'YY', 'ZZZ']

我的算法如下：

• 调用一个helper方法，如果存在这样的组合，则返回该组合
• helper方法获取输出中所需的卡片列表和卡片数量
• 基本情况：如果计数为0，则返回true和空数组(这意味着我们没有更多的牌可挑选(
• 迭代每张卡
• 找到count-1张牌的组合，当前牌被拾取(递归(
• 如果找到组合，请检查当前卡以确保它可以添加到当前组合中并返回
• 如果你已经迭代了所有的牌，但找不到组合，那么用空数组返回false

def unique_cards(cards, count)
can, picked_cards = _unique_cards(cards, count)
puts can ? picked_cards : false
end
def _unique_cards(cards, count)
return [true, []] if count == 0
cards.each do |card|
card_length = card.length
card_type = card[0]
remaining_cards = cards - [card]
can, selected_cards = _unique_cards(remaining_cards, count - 1)
if can
can_be_added = (selected_cards.all? { |c1| c1.length == card_length } || selected_cards.all? { |c1| c1[0] == card_type }) && (selected_cards.all? { |c1| c1.length != card_length   } || selected_cards.all? { |c1| c1[0] != card_type })
if can_be_added
selected_cards << card
return [true, selected_cards]
end
end
end
return [false, []]
end

Answer 1

require 'set'
def find_em(arr, n)
arr.combination(n)
.select do |a|
[1, n].include?(a.map { |s| s[0] }.uniq.size) &&
[1, n].include?(a.map(&:size).uniq.size)
end.uniq(&:to_set)
end

find_em ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX', 'Y'], 3
#=> [["Y", "Y", "Y"], ["Y", "Z", "X"]]
find_em ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
#=> [["X", "YY", "ZZZ"]]
find_em ['X', 'Y', 'YY', 'ZZ', 'ZZ'], 3
#=> []

在第一个例子中，如果没有.uniq(&:to_set)，我们将获得

find_em ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX', 'Y'], 3
#=> [["Y", "Y", "Y"], ["Y", "Z", "X"], ["Y", "Z", "X"], ["Z", "X", "Y"]]

请参见数组#组合和数组#uniq。