PathGen

Edge = Struct.new(:nd,:ed)
class Node
    attr_accessor :visited,:cons,:st,:bad
    def initialize(st)
        @st = st
        @cons = []
        @visited = Hash.new(false)
    end
    def addlink(obj)
        @cons << obj
    end
end
t = gets.chomp
a = t.split ""
a.uniq!
t = gets
b = t.to_i - 1
x = (a*b).combination(b).to_a.uniq
nmap = {}
x.each do |el|
    nmap[el.join","] = Node.new(el.join",")
end
x.each do |el|
    a.each do |it|
        nmap[el.join","].addlink(Edge.new(nmap[(el[1..-1] << it).join","],it))
    end
end

visited = Hash.new(false)
notvisited = nmap.values
path = []
currp = []
edges = []
curredges = []
index = 0
cnode = nmap[x[0].join","]
currp << cnode
while notvisited.length > 0
    e = true
    nnode = nil
    if visited[cnode]
    end
    cnode.cons.each do |con|
        if not cnode.visited[con]
            cnode.visited[con] = true
            nnode = con.nd
            currp << nnode
            curredges << con
            e = false
            break
        end
    end
    if e
        visited[cnode] = true
        notvisited.delete cnode
        path[index,0]=currp.clone
        edges[index,0]=curredges.clone
        index = nil
        i = -1
        while index.nil?
            i+=1
            index = path.index(notvisited[i])
            if i > notvisited.length
                break
            end
        end
        cnode = notvisited[i]
        currp = []
        curredges = []
        next
    end
    cnode = nnode
end
edges.each do |edge|
    print edge.ed
end
puts