将字符串拆分成n个子字符串的可能方法

Question

我将尝试编写一个方法，它将以'abcd'作为输入，并返回：

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

所以，将字符串分成n个子字符串的所有可能方式，使得当你连接s1 + s2 + s3 + ...时，你会得到原始字符串。

我已经这样解决了它，但我觉得应该有一种更快更直接的方法来做到这一点。

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

有什么建议吗？

- Navid Falla

---

请参见以下链接：https://dev59.com/kFnUa4cB1Zd3GeqPc60R - Mark Thomas

Answer 1

一个使用repeated_permutation的单行代码（我刚从你那里学到它）：

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 生成像 [" ", "", " "] 的联合体。
• zip 将它们与字母成对，如 [["a", " "], ["b", ""], ["c", " "], ["d", nil]]。
• join 将所有部分转换为字符串并连接它们，如 "a bc d"。

请注意，nil 变为空字符串，并且join 会递归地工作，有效地将整个结构压扁。

---

在我还不知道 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"]

所有这些的基本思想都是这样的（为了清晰起见，使用硬编码字符串）：

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

- Stefan Pochmann

---

这绝对是最漂亮的答案！（repeated_permutation one），但我不太明白它为什么有效... - Navid Falla

非常聪明，Stefan。一个细节：你可以用arr.zip(j).join替换s.chars.zip(j).join，其中arr已经被预先定义为arr = s.chars。 - Cary Swoveland

@NavidFallad 我添加了一些解释，希望现在清楚了？你可以随时尝试一下，例如将块更改为{ |j| p s.chars.zip(j) }，以查看发生了什么。当然，文档也是有帮助的 :-). - Stefan Pochmann

@CarySwoveland 是的，这样做可以使它更快，但它仍然是较慢的之一，所以我并不试图赢得速度奖，只是想赢得简洁和清晰奖 :-) - Stefan Pochmann

Answer 2

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

这是另一种方法（在字符串中添加空格）。

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

- Cary Swoveland

Answer 3

以下是不同方法之间的比较：

#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

结果

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

使用更长的字符串：

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

- Sagar Pandya

---

对于 stefan_3，您使用了 stefan2。顺便说一下，我添加了第四个，现在我不知道哪个是哪个 :-）。我认为排序不应该包含在基准测试中，这可能会对时间产生重大影响。甚至可能会对不同的解决方案产生不同的影响，具体取决于它们的结果已经排序的方式。 - Stefan Pochmann

@StefanPochmann 好的，已更新。我必须对汤姆的答案进行排序，否则结果会不同。 - Sagar Pandya

现在这是一个社区维基答案。如果有人认为测试需要改进，可以在答案中找到测试代码的链接。 - Sagar Pandya

那确实是快速的工作！我将在我的答案中添加另一种方法。你可能想把它加入到混合物中。 - Cary Swoveland

@CarySwoveland不需要使用sort，reverse就足够了，并且开销要小得多。或者他可以使用[str + space_c, str + c]直接生成“正确”的顺序。顺便说一句，虽然这个“Fruity”输出看起来很可爱，但我实际上更喜欢所有东西都是冷酷的数字，而不仅仅是“相似”。特别是当几个“相似”被链接在一起时，因为相似性听起来并不具有传递性。 - Stefan Pochmann

Answer 4

这实际上是一个相当棘手的问题...但经过一番思考，我想出了一个聪明的方法。它可能不是最紧凑（单行）的解决方案；但它非常有教育意义，可以轻松地用任何语言重写，并且不浪费空间。

首先要认识到，对于长度为n的输入字符串，有n-1个可能的插入空格的位置。所以，我们需要做的就是：

1. 生成这n-1个位置的所有可能组合，然后 2. 相应地插入这些空格。

对于第一部分，我使用了一个简单的算法来生成(1..n-1).to_a的幂集，其中n是输入字符串的长度：

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

例如：

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

现在，我们可以简单地在原始字符串中在这些索引处插入空格。我添加的一个小技巧是从较大的索引开始，这样不会破坏其他索引 - 也就是说，您需要按降序使用每个列表。

以下是最终代码：

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

使用方法：

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

- Tom Lord

---

附注：breakdown(string).length == 2**(string.length-1)。例如，breakdown("abcdefghijklmnopqrstuvwxyz").length == 33554432！这个算法呈指数增长（这一点并不奇怪，因为它基于幂集计算），因此对于大型输入来说，计算此列表很快变得不切实际。 - Tom Lord