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

Question

所以我一直在尝试解决这个问题，并且有点坚持使用回溯来实现它，并且真的很想了解我在这里做错了什么。我怀疑我的问题与方法中通过引用传递的数组有关，但我似乎无法理解。任何帮助表示赞赏。这是在面试中被问到的，我正在尝试自己解决。

这里是问题：

卡片有套间和重复时间。给定一张卡片列表和输出大小，return 一张卡片列表

（全部相同字母或全部不同字母）& （所有相同的长度或所有不同的字母长度）。

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']

我的算法如下：

调用辅助方法 returns 如果存在这样的组合并且组合
辅助方法在需要的输出中获取卡片列表和卡片数量
基本情况：return 如果计数为 0（意味着我们没有更多卡片可供选择），则为真和空数组
遍历每张卡片
找到一个计数的组合 - 1 张卡片，当前卡片被选中（递归）
如果找到组合，请检查当前卡以确保它可以添加到当前组合，并且return
如果您遍历了所有卡片但找不到组合，return false with empty array

  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"]]

参见 Array#combination and Array#uniq。

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

Backtracking and combinatronics problem in Ruby

ruby

recursion

combinatorics

backtracking