Блог

Главная - Вопросы по программированию - комбинации подстрок в строке

комбинации подстрок в строке

#ruby #combinations

#ruby #комбинации

Вопрос:

Как я могу найти все возможные комбинации набора строк в данной строке?

 strings = ["ab","aa","ab","bb","ba","aba","aab"]
given_string = "abaababbab"

должен возвращать:

 [
 ["ab","aa","ba","bb","ab],
 ["ab","aab","ab","ba","bab"]
 ["aba","aba","bb","ab"]
]

Комментарии:

1. Вы имеете в виду все комбинации символов (например, «abc» вернет «abc», «acb», bac», «bca», cba»), вы имеете в виду все конкатенации всех строк (например, [«dog», «cat»] возвращает [«dogcat», «catdog»], или все комбинации всех символов и все конкатенации?

2. как это может быть «bab» в вашем возврате, если strings не включает «bab»?

3. Похоже, что это вызывает рекурсивную функцию (прошу прощения, если вы уже зашли так далеко). Приветствия!

Ответ №1:

Приблизительная идея может быть примерно такой:

 strings.select do |s|
  given_string.index(s)
end

Это дало бы вам:

 ["ab", "aa", "ab", "bb", "ba", "aba", "aab"]

Я не уверен, ищете ли вы здесь дубликаты или нет. Вы можете столкнуться с вычислительно сложной проблемой, если не будете осторожны, поскольку именно такого рода вещи делают секвенирование ДНК чрезвычайно трудоемким с точки зрения вычислений.

Ответ №2:

Следующее:

 strings = ["ab","aa","ab","bb","ba","aba","aab"]
@strings = strings.uniq!
@given_string = 'abaababbab'
@given_length = @given_string.length

def parse
  @parses.each do |parse|
    before = parse.pop # offset of the part that hasn't yet been parsed
    @strings.each do |str|
      next unless m = @given_string.match(str, before)
      first, last = m.offset(0)
      next unless first == before
      if last == @given_length
        @completed_parses.push([*parse, str])
      else
        @new_parses.push([*parse, str, last])
      end
    end
  end
  @parses = @new_parses
  @new_parses = []
  parse unless @parses.empty?
end

@parses = [[0]]
@new_parses = []
@completed_parses = []
parse
p @completed_parses

даст вам:

 [["aba", "aba", "bb", "ab"], ["ab", "aa", "ba", "bb", "ab"]]

Я не понимаю, почему у вас есть ["ab","aab","ab","ba","bab"] в вашем ответе.