Given a word, I need to get all variations of spaces for that word

Question

Given a word, let's use "Stack", I want to get all variations of that word with spaces.

For example, I would be looking for an array like:

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

I don't have any code to show as I am not able to solve this issue. I have a feeling I need to split the word at each letter and use a loop to add a space, then add that word to an array but I'm not sure of the logic behind this. I'm assuming I would need to use modulus % but again, I don't really know.

I'm using Ruby for this but given that this is more of a logic question it doesn't really matter which language is used.

Answer 1

Following up the comment by Jörg W Mittag:

'Stack'.
  split(//).
  map { |l| [l, "#{l} "] }.
  reduce(&:product).
  map(&:join)

Answer 2

Here is a recursive solution.

Code

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

Example

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

Explanation

The steps performed by this method are shown below. Note that each time recurse is called the printed lines are indented by 4 spaces.

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

prints

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

Variant of @Marcin's answer

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

See Integer#bit_length and Integer#[].

We can map each number n in the range (0..2**last_idx-1) to one element of the desired array by examining n's bits. Specifically, if the ith significant bit is 1 the character word[word.size-1-i] will be prepended by a space; if it is 0 that character will not be prepended by a space.

For word = 'Stack', last_idx = 'Stack'.size-1 #=> 4, so the range is 0..2**4-1 #=> 0..15. These numbers correspond to the binary numbers 0, 0b1, 0b10, 0b11, 0b110,...0b1111. One number in this range is 11, whose binary representation is given by 11.to_s(2) #=> "1011" or 0b1011. Since the third least significant is 0, "a" in "Stack" will remain unchanged, but "t", "c" and "k" will be respectively mapped to " t", " c" and " k" (since they correspond to 1's in 0b1011), producing the string ["S", " t", "a", " c", " k"].join #=> => "S ta c k".

Notice how this this technique is more-or-less equivalent to using the method Array#combination.

Answer 3

Other option using indexes, one liner:

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

Answer 4

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

produces

["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 is an array of all indices to put our delimiter, i.e.

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

Calling reverse while iterating over the combinations to insert delimiter from the end, so the indices will keep matching while going backwards.