possible ways of splitting a string into n substrings

Question

I'm trying to write a method that would take 'abcd' as an input, and return:

["a b c d", "a b cd", "a bc d", "a bcd", "ab c d", "ab cd", "abc d", "abcd"]

so, all possible ways of splitting a string into n substrings that when you concatenage s1 + s2 + s3 + ... you get back the original string.

I have solved it like this, but I feel like there should be a faster and more straightforward way to do it.

def sequence(n)
  [true, false].repeated_permutation(n).to_a
end

def breakdown4(string)
  guide = sequence(string.length-1)
  arr = []
  guide.each do |i|
    s = string.dup
    counter = 0
    i.each do |j|
      if j
        s.insert(counter+1, " ")
        p counter
        counter += 2
      else
        counter += 1
      end
    end
    arr.push(s)
  end
  arr
end

any suggestions?

Answer 1

Here are some comparisons between the different methods:

#navid
def sequence(n)
  [true, false].repeated_permutation(n).to_a
end

def breakdown4(string)
  guide = sequence(string.length-1)
  arr = []
  guide.each do |i|
    s = string.dup
    counter = 0
    i.each do |j|
      if j
        s.insert(counter+1, " ")
        #p counter
        counter += 2
      else
        counter += 1
      end
    end
    arr.push(s)
  end
  arr
end


#tom
def powerset(arr)
  a = [[]] 
  for i in 0...arr.size do
    len = a.size; j = 0;
    while j < len
      a << (a[j] + [arr[i]])
      j+=1
    end
  end
  a
end

def breakdown(string)
  indexes_lists = powerset((1..string.length-1).to_a)
  indexes_lists.map(&:reverse).map do |indexes_list|
    result = string.dup
    indexes_list.each { |i| result.insert(i, " ")}
    result
  end
end

#stefan
def stefan1 s
  [s[0]].product(*s[1..-1].chars.flat_map { |c| [[' ', ''], [c]] }).map(&:join)
end

def stefan2 s
  s[1..-1].chars.reduce([s[0]]) { |m, c| m.product([' ', ''], [c]) }.map(&:join)
end

def stefan3 s
  [''].product(*([[' ', '']] * s.size.pred)).map { |j| s.gsub('') { j.shift } }
end

def stefan4 s
  (0...2**s.size).step(2).map { |i| s.gsub(/(?!^)/) { ' ' * (1 & i /= 2) } }
end

def stefan5 s
  [' ', ''].repeated_permutation(s.size - 1).map { |j| s.chars.zip(j).join }
end

#cary
def cary s
  s[1..-1].each_char.reduce([s[0]]) do |arr, c|
    space_c = ' ' + c 
    arr.flat_map { |str| [str + c, str + space_c] }
  end
end

#cary2
def cary2 s
  arr = (1..s.size-1).to_a
    #=> [1, 2, 3]
  s.size.times.flat_map do |n|
    arr.combination(n).map do |locs|
      scopy = s.dup
      locs.reverse_each { |idx| scopy.insert(idx, ' ') }
      scopy
    end
end  
end

Results

require 'fruity'
str = 'abcd'

compare do
  navid    { s = str.dup; breakdown4(s) }
  tom      { s = str.dup; breakdown(s).sort }
  stefan_1 { s = str.dup; stefan1(s) }
  stefan_2 { s = str.dup; stefan2(s) }
  stefan_3 { s = str.dup; stefan3(s) }  
  stefan_4 { s = str.dup; stefan4(s).sort }
  stefan_5 { s = str.dup; stefan5(s) }
  cary_s   { s = str.dup; cary(s).reverse  }  
  cary_s2  { s = str.dup; cary2(s).sort  }  
end

#Running each test 64 times. Test will take about 1 second.
#cary_s is faster than navid by 2x ± 1.0
#navid is similar to tom
#tom is similar to cary_s2
#cary_s2 is similar to stefan_1
#stefan_1 is similar to stefan_2
#stefan_2 is faster than stefan_3 by 2x ± 1.0
#stefan_3 is similar to stefan_5
#stefan_5 is similar to stefan_4

Using a longer string:

str = 'abcdefghijklm'

#Running each test once. Test will take about 4 seconds.
#cary_s is faster than stefan_1 by 9x ± 1.0
#stefan_1 is similar to cary_s2
#cary_s2 is similar to navid
#navid is similar to tom
#tom is similar to stefan_2
#stefan_2 is faster than stefan_3 by 2x ± 1.0
#stefan_3 is similar to stefan_5
#stefan_5 is similar to stefan_4

Answer 2

A oneliner also using repeated_permutation (which I just learned from you :-):

s = 'abcd'

[' ', ''].repeated_permutation(s.size - 1).map { |j| s.chars.zip(j).join }
=> ["a b c d", "a b cd", "a bc d", "a bcd", "ab c d", "ab cd", "abc d", "abcd"]

• repeated_permutation produces joints, like [" ", "", " "].
• zip pairs them to the letters, like [["a", " "], ["b", ""], ["c", " "], ["d", nil]].
• join turns all parts into strings and joins them, like "a bc d".

(Note that nil becomes the empty string and that join works recursively, effectively flattening the whole structure).

---

Previous solutions I came up with before I knew repeated_permutation:

[s[0]].product(*s[1..-1].chars.flat_map { |c| [[' ', ''], [c]] }).map(&:join)
=> ["a b c d", "a b cd", "a bc d", "a bcd", "ab c d", "ab cd", "abc d", "abcd"]

s[1..-1].chars.reduce([s[0]]) { |m, c| m.product([' ', ''], [c]) }.map(&:join)
=> ["a b c d", "a b cd", "a bc d", "a bcd", "ab c d", "ab cd", "abc d", "abcd"]

[''].product(*([[' ', '']] * s.size.pred)).map { |j| s.gsub('') { j.shift } }
=> ["a b c d", "a b cd", "a bc d", "a bcd", "ab c d", "ab cd", "abc d", "abcd"]

(0...2**s.size).step(2).map { |i| s.gsub(/(?!^)/) { ' ' * (1 & i /= 2) } }
=> ["abcd", "a bcd", "ab cd", "a b cd", "abc d", "a bc d", "ab c d", "a b c d"]

The basic idea of all of them is like this (using the hardcoded string for clarity):

['a'].product([' ', ''], ['b'], [' ', ''], ['c'], [' ', ''], ['d']).map(&:join)
=> ["a b c d", "a b cd", "a bc d", "a bcd", "ab c d", "ab cd", "abc d", "abcd"]

Answer 3

s = 'abcd'

s[1..-1].each_char.reduce([s[0]]) do |arr, c|
  space_c = " #{c}" 
  arr.flat_map { |str| [str + c, str + space_c] }
end
  # => ["abcd", "abc d", "ab cd", "ab c d", "a bcd", "a bc d", "a b cd", "a b c d"]

Here's another way (stuffing spaces into the string).

arr = (1..s.size-1).to_a
  #=> [1, 2, 3]
s.size.times.flat_map do |n|
  arr.combination(n).map do |locs|
    scopy = s.dup
    locs.reverse_each { |idx| scopy.insert(idx, ' ') }
    scopy
  end
end  
  #=> ["abcd", "a bcd", "ab cd", "abc d", "a b cd", "a bc d", "ab c d", "a b c d"]

Answer 4

This is actually quite a tricky problem... But after giving it some thought, here's a clever approach I came up with. It may not be the most compact (one-liner) solution; but it's quite instructive, could easily be rewritten in any language, and is non-wasteful.

Start by recognising that, given an input string of length n, there are n-1 possible places to insert a space. So, all we need to do is:

1. Generate all possible combinations of those n-1 positions, then
2. Insert those spaces accordingly.

For part (1), I used a simple algorithm to generate the powerset of (1..n-1).to_a, where n is the input string length:

def powerset(arr)
  a = [[]] 
  for i in 0...arr.size do
    len = a.size; j = 0;
    while j < len
      a << (a[j] + [arr[i]])
      j+=1
    end
  end
  a
end

For example:

powerset([1,2,3])
#=> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Now, we can simply insert spaces to the original string at those indexes. One small trick I added is by starting at the larger index, it doesn't mess up the other indexes - i.e. you need to use each list in descending order.

Here's the final code:

def powerset(arr)
  a = [[]] 
  for i in 0...arr.size do
    len = a.size; j = 0;
    while j < len
      a << (a[j] + [arr[i]])
      j+=1
    end
  end
  a
end

def breakdown(string)
  indexes_lists = powerset((1..string.length-1).to_a)
  indexes_lists.map(&:reverse).map do |indexes_list|
    result = string.dup
    indexes_list.each { |i| result.insert(i, " ")}
    result
  end
end

Usage:

breakdown("abcde")
# => ["abcde", "a bcde", "ab cde", "a b cde", "abc de",
#     "a bc de", "ab c de", "a b c de", "abcd e", "a bcd e",
#     "ab cd e", "a b cd e", "abc d e", "a bc d e", "ab c d e",
#     "a b c d e"]