Как разбить строку на последовательные подстроки длиной не более 3 всеми возможными способами?

Question

Я пытаюсь взять строку длиной от 1 до 10 и вывести все возможные способы разбиения строки на последовательные подстроки размером 1, 2 или 3. Например:

Input: 123456

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

    [1, 2, 3, 4, 5, 6]  
    [12, 3, 4, 5, 6]  
    [1, 23, 4, 5, 6]  
    [1, 2, 34, 5, 6]  
    [1, 2, 3, 45, 6]  
    [1, 2, 3, 4, 56]  
    [12, 34, 5, 6]  
    [12, 3, 45, 6]  
    [12, 3, 4, 56]  
    [1, 23, 45, 6]  
    [1, 2, 34, 56]  
    [1, 23, 4, 56]  
    [12, 34, 56]  
    [123, 4, 5, 6]  
    [1, 234, 5, 6]  
    [1, 2, 345, 6]  
    [1, 2, 3, 456]  
    [123, 456]  
    [1, 23, 456]  
    [1, 234, 56]  
    [12, 345, 6]  
    [12, 3, 456]  
    [123, 4, 56]  
    [123, 45, 6]

Я пытаюсь сделать это в рубине. Спасибо!

Answer 1

Вот рабочая функция. Может быть не оптимальным, так как я не тратил на это много времени.

str = "1234567890"

def f(s, n)
    return [[]] if s.empty?

    (1..[n, s.length].min).map{|c| f(s[c..-1], n).map{|a| [s[0, c]] + a}}.inject(&:+)
end

puts f(str, 3).collect{|l| l * "\t"}

РЕДАКТИРОВАТЬ: сделал его немного короче, а длина теперь передается в качестве второго параметра для гибкости.

Answer 2

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

def combinations(s)
  c = (s.length > 3) ? [] : [[s]]
  max = [4, s.length].min
  (1...max).inject(c) do |c, i|
    combinations(s[i..-1]).inject(c) do |c, tail|
      c.push([s[0...i]] + tail)
    end
  end
end

combinations("12345").each { |c| p c }

Производит:

["1", "2", "345"]
["1", "2", "3", "45"]
["1", "2", "3", "4", "5"]
["1", "2", "34", "5"]
["1", "23", "45"]
["1", "23", "4", "5"]
["1", "234", "5"]
["12", "345"]
["12", "3", "45"]
["12", "3", "4", "5"]
["12", "34", "5"]
["123", "45"]
["123", "4", "5"]

Answer 3

Вот еще:

class String
  def splitup(prefix=nil)
    parts = []
    if size <= 3
      parts << [prefix,self].compact * ","
    end
    (1..([size,3].min)).each do |p|
      next if p >= size
      parts << slice(p..-1).splitup([prefix,slice(0,p)].compact * ",")
    end
    parts
  end

  def report
    flat = splitup.flatten.sort_by {|x| [-x.size,x]}
    puts
    puts "#{flat.size} permutations of #{self}"
    puts flat
  end
end

, а затем

>> "123456".report

24 permutations of 123456
1,2,3,4,5,6
1,2,3,4,56
1,2,3,45,6
1,2,34,5,6
1,23,4,5,6
12,3,4,5,6
1,2,3,456
1,2,34,56
1,2,345,6
1,23,4,56
1,23,45,6
1,234,5,6
12,3,4,56
12,3,45,6
12,34,5,6
123,4,5,6
1,23,456
1,234,56
12,3,456
12,34,56
12,345,6
123,4,56
123,45,6
123,456

Answer 4

def f(s, mx)
  (1..[s.size, mx].min).each_with_object([]) do |n,a|
     if n < s.size
       sf = s[0, n]
       f(s[n..-1], mx).each { |c| a << [sf, *c] }
     else
       a << [s]
     end
  end
end

f("12345", 3)
  #=> [["1", "2", "3", "4", "5"], ["1", "2", "3", "45"],
  #    ["1", "2", "34", "5"], ["1", "2", "345"], ["1", "23", "4", "5"],
  #    ["1", "23", "45"], ["1", "234", "5"], ["12", "3", "4", "5"],
  #    ["12", "3", "45"], ["12", "34", "5"], ["12", "345"],
  #    ["123", "4", "5"], ["123", "45"]] => [["1", "2", "3", "4"],
  #    ["1", "2", "34"], ["1", "23", "4"], ["1", "234"],
  #    ["12", "3", "4"], ["12", "34"], ["123", "4"]]