Учитывая слово, мне нужно получить все варианты пробелов для этого слова - PullRequest
Новая
       22

Учитывая слово, мне нужно получить все варианты пробелов для этого слова

0 голосов
/ 24 ноября 2018

Учитывая слово, давайте использовать «Стек», я хочу получить все варианты этого слова с пробелами.

Например, я бы искал такой массив: 

[
  'S tack',
  'S t ack',
  'S t a ck',
  'S t a c k',
  'Stac k',
  'Sta c k',
  'St a c k',
   ...
]

У меня нет кода для отображения, так как я не могу решить эту проблему.У меня такое чувство, что мне нужно разделить слово на каждую букву и использовать цикл, чтобы добавить пробел, а затем добавить это слово в массив, но я не уверен в логике этого.Я предполагаю, что мне нужно было бы использовать модуль %, но опять же, я не совсем знаю.

Я использую Ruby для этого, но, учитывая, что это скорее логический вопрос, он недействительно важно, какой язык используется.

Ответы [ 4 ]

0 голосов
/ 25 ноября 2018

После комментария от Jörg W Mittag: 

'Stack'.
  split(//).
  map { |l| [l, "#{l} "] }.
  reduce(&:product).
  map(&:join)
0 голосов
/ 24 ноября 2018

Вот рекурсивное решение.

Код 

def recurse(word)
  return [word] if word.size == 1
  first_char = word[0]
  recurse(word[1..-1]).flat_map { |s| [first_char+s, first_char+' '+s] }
end

Пример 

arr = recurse 'Stack'
  #=> ["Stack", "S tack", "St ack", "S t ack", "Sta ck", "S ta ck", "St a ck", "S t a ck",
  #    "Stac k", "S tac k", "St ac k", "S t ac k", "Sta c k", "S ta c k", "St a c k", 
  #    "S t a c k"]

Пояснение

Шаги, выполняемые этим методом, показаны ниже.Обратите внимание, что каждый раз, когда вызывается recurse, напечатанные строки имеют отступ в 4 пробела. 

INDENT = 4
@off = 0

def s
  ' '*@off
end

def indent
  @off += INDENT
end

def undent
  @off -= INDENT
end

def recurse(word)
  puts "#{s}Entering recurse(\"#{word}\")"
  puts "#{s}Returning [\"#{word}\"] as \"#{word}\".size == 1" if word.size == 1
  return [word] if word.size == 1
  puts "#{s}Calling recurse(\"#{word[1..-1]}\")"
  indent
  a1 = recurse(word[1..-1])
  undent
  puts "#{s}recurse(\"#{word[1..-1]}\") returned a1 = #{a1}"
  first_char = word[0]
  puts "#{s}first_char = \"#{first_char}\""
  a2 = a1.flat_map { |s| [first_char+s, first_char+' '+s] }
  puts "#{s}Returning a1.flat_map { |s| first_char+s, first_char + ' ' + s] } = "
  puts "#{s}  #{a2}"   
  a2
end

recurse("dogs")
  #=> ["dogs", "d ogs", "do gs", "d o gs", "dog s", "d og s", "do g s", "d o g s"]

отпечатков 

Entering recurse("dogs")
Calling recurse("ogs")
    Entering recurse("ogs")
    Calling recurse("gs")
        Entering recurse("gs")
        Calling recurse("s")
            Entering recurse("s")
            Returning ["s"] as "s".size == 1
        recurse("s") returned a1 = ["s"]
        first_char = "g"
        Returning a1.flat_map { |s| first_char+s, first_char + ' ' + s] } =
          ["gs", "g s"]
    recurse("gs") returned a1 = ["gs", "g s"]
    first_char = "o"
    Returning a1.flat_map { |s| first_char+s, first_char + ' ' + s] } =
      ["ogs", "o gs", "og s", "o g s"]
recurse("ogs") returned a1 = ["ogs", "o gs", "og s", "o g s"]
first_char = "d"
Returning a1.flat_map { |s| first_char+s, first_char + ' ' + s] } =
  ["dogs", "d ogs", "do gs", "d o gs", "dog s", "d og s", "do g s", "d o g s"]

Вариант ответа @ Marcin 

word = 'Stack'
word_chars = word.chars
last_idx = word.size-1
(0..2**last_idx-1).map do |n|
  n.bit_length.times.with_object(word_chars.dup) do |i,arr|
    c = arr[last_idx-i]
    arr[last_idx-i] = n[i] == 1 ? (' '+c) : c
  end.join
end
  #=> ["Stack", "Stac k", "Sta ck", "Sta c k", "St ack", "St ac k", "St a ck",
  #    "St a c k", "S tack", "S tac k", "S ta ck", "S ta c k", "S t ack", "S t ac k",
  #    "S t a ck", "S t a c k"]

См. Integer # bit_length и Integer # [] .

Мы можем сопоставить каждое число n в диапазоне (0..2**last_idx-1) содин элемент нужного массива, проверяя биты n.В частности, если i значащий бит равен 1, к символу word[word.size-1-i] будет добавлен пробел;если это 0, то этому символу не будет предшествовать пробел.

Для word = 'Stack', last_idx = 'Stack'.size-1 #=> 4, поэтому диапазон равен 0..2**4-1 #=> 0..15.Эти числа соответствуют двоичным числам 0, 0b1, 0b10, 0b11, 0b110,...0b1111.Одно число в этом диапазоне - 11, двоичное представление которого дается 11.to_s(2) #=> "1011" или 0b1011.Поскольку третьим наименее значимым является 0, "a" в "Stack" останется неизменным, но "t", "c" и "k" будут соответственно сопоставлены с " t", " c" и " k" (так как они соответствуют 1 в 0b1011), получая строку ["S", " t", "a", " c", " k"].join #=> => "S ta c k".

Обратите внимание, что этот метод более или менее эквивалентен использованию метода Array # комбинация.

0 голосов
/ 25 ноября 2018

Другой вариант с использованием индексов, один вкладыш: 

string = 'Stack'

(1..string.size).map.with_object([]) { |n, res| (1..string.size-1).to_a.combination(n).map { |idxs| idxs.reverse.each.with_object(string.dup) { |i, tmp| res << tmp.insert(i, ' ') } } }.uniq

#=> ["S tack", "St ack", "Sta ck", "Stac k", "S t ack", "S ta ck", "S tac k", "St a ck", "St ac k", "Sta c k", "S t a ck", "S t ac k", "S ta c k", "St a c k", "S t a c k"]
0 голосов
/ 24 ноября 2018 
def combine_string_with(s, delimiter = " ")
  combinations = (1..s.size - 1).flat_map { |n| (1..s.size - 1).to_a.combination(n).to_a }
  combinations.map do |arr|
    arr.reverse.each_with_object(s.dup) do |i, string|
      string.insert(i, delimiter)
    end
  end
end

combine_string_with("Stack")

производит 

["S tack",
 "St ack",
 "Sta ck",
 "Stac k",
 "S t ack",
 "S ta ck",
 "S tac k",
 "St a ck",
 "St ac k",
 "Sta c k",
 "S t a ck",
 "S t ac k",
 "S ta c k",
 "St a c k",
 "S t a c k"]

combinations - это массив всех индексов для установки нашего разделителя, то есть 

[[1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Вызов reverse при переборе комбинаций длявставьте разделитель в конце, чтобы индексы продолжали совпадать при движении назад.

...