gistfile1.rb

def add_to_substrings(substrings, candidate, count)
  substrings[candidate] += count if substrings[candidate]
  substrings[candidate] = count
end

STRING = "aaabbbababcdd"
MIN_SUPORT = 2

candidates = []
substrings = {}

# first candidates
candidates = STRING.chars.to_a.uniq

STRING.size.times do |i|
  puts "= Round: #{i}"
  puts "== Candidates: #{candidates}"
  puts "== Substrings: #{substrings}"


  for candidate in candidates
    support = STRING.scan(candidate).size

    add_to_substrings(substrings, candidate, support) if support >= MIN_SUPORT
  end

  candidates = substrings.keys.permutation(i+1).map{|a| a.join}
  break if candidates.empty?
end


#output
= Round: 0
== Candidates: ["a", "b", "c", "d"]
== Substrings: {}
= Round: 1
== Candidates: ["a", "b", "d"]
== Substrings: {"a"=>5, "b"=>5, "d"=>2}
= Round: 2
== Candidates: ["ab", "ad", "ba", "bd", "da", "db"]
== Substrings: {"a"=>5, "b"=>5, "d"=>2}
= Round: 3
== Candidates: ["abd", "abab", "abba", "adb", "adab", "adba", "aabb", "aabd", "aabba", "abab", "abad", "abaab", "bad", "baab", "baba", "bda", "bdab", "bdba", "baba", "babd", "babba", "bbaa", "bbad", "bbaab", "dab", "daab", "daba", "dba", "dbab", "dbba", "daba", "dabb", "dabba", "dbaa", "dbab", "dbaab", "abab", "abad", "ababa", "abba", "abbd", "abbba", "abda", "abdb", "abdba", "abbaa", "abbab", "abbad", "baab", "baad", "baaab", "baba", "babd", "babab", "bada", "badb", "badab", "baaba", "baabb", "baabd"]
== Substrings: {"a"=>5, "b"=>5, "d"=>2, "ab"=>3, "ba"=>2}
= Round: 4
== Candidates: ["abdab", "abdba", "ababd", "ababba", "abbad", "abbaab", "adbab", "adbba", "adabb", "adabba", "adbab", "adbaab", "aabbd", "aabbba", "aabdb", "aabdba", "aabbab", "aabbad", "ababd", "ababab", "abadb", "abadab", "abaabb", "abaabd", "badab", "badba", "baabd", "baabba", "babad", "babaab", "bdaab", "bdaba", "bdaba", "bdabba", "bdbaa", "bdbaab", "babad", "bababa", "babda", "babdba", "babbaa", "babbad", "bbaad", "bbaaab", "bbada", "bbadab", "bbaaba", "bbaabd", "dabab", "dabba", "daabb", "daabba", "dabab", "dabaab", "dbaab", "dbaba", "dbaba", "dbabba", "dbbaa", "dbbaab", "dabab", "dababa", "dabba", "dabbba", "dabbaa", "dabbab", "dbaab", "dbaaab", "dbaba", "dbabab", "dbaaba", "dbaabb", "ababd", "ababba", "abadb", "abadba", "ababab", "ababad", "abbad", "abbaba", "abbda", "abbdba", "abbbaa", "abbbad", "abdab", "abdaba", "abdba", "abdbba", "abdbaa", "abdbab", "abbaab", "abbaad", "abbaba", "abbabd", "abbada", "abbadb", "baabd", "baabab", "baadb", "baadab", "baaabb", "baaabd", "babad", "babaab", "babda", "babdab", "bababa", "bababd", "badab", "badaab", "badba", "badbab", "badaba", "badabb", "baabab", "baabad", "baabba", "baabbd", "baabda", "baabdb"]
== Substrings: {"a"=>5, "b"=>5, "d"=>2, "ab"=>3, "ba"=>2}
= Round: 5
== Candidates: ["abdabba", "abdbaab", "ababdba", "ababbad", "abbadab", "abbaabd", "adbabba", "adbbaab", "adabbba", "adabbab", "adbabab", "adbaabb", "aabbdba", "aabbbad", "aabdbba", "aabdbab", "aabbabd", "aabbadb", "ababdab", "abababd", "abadbab", "abadabb", "abaabbd", "abaabdb", "badabba", "badbaab", "baabdba", "baabbad", "babadab", "babaabd", "bdaabba", "bdabaab", "bdababa", "bdabbaa", "bdbaaab", "bdbaaba", "babadba", "bababad", "babdaba", "babdbaa", "babbaad", "babbada", "bbaadab", "bbaaabd", "bbadaab", "bbadaba", "bbaabad", "bbaabda", "dababba", "dabbaab", "daabbba", "daabbab", "dababab", "dabaabb", "dbaabba", "dbabaab", "dbababa", "dbabbaa", "dbbaaab", "dbbaaba", "dababba", "dababab", "dabbaba", "dabbbaa", "dabbaab", "dabbaba", "dbaabab", "dbaaabb", "dbabaab", "dbababa", "dbaabab", "dbaabba", "ababdba", "ababbad", "abadbba", "abadbab", "abababd", "ababadb", "abbadba", "abbabad", "abbdaba", "abbdbaa", "abbbaad", "abbbada", "abdabba", "abdabab", "abdbaba", "abdbbaa", "abdbaab", "abdbaba", "abbaabd", "abbaadb", "abbabad", "abbabda", "abbadab", "abbadba", "baabdab", "baababd", "baadbab", "baadabb", "baaabbd", "baaabdb", "babadab", "babaabd", "babdaab", "babdaba", "bababad", "bababda", "badabab", "badaabb", "badbaab", "badbaba", "badabab", "badabba", "baababd", "baabadb", "baabbad", "baabbda", "baabdab", "baabdba"]
== Substrings: {"a"=>5, "b"=>5, "d"=>2, "ab"=>3, "ba"=>2}