散列映射按如下方式填充：
{"1"=>["2"], "2"=>["3", "7"], "3"=>["4"], "5"=>["6", "2"], "6"=>["7"], "7"=>["8", "4"]}
使得每个键可以具有多个值。这些值表示一组路线的公交车站，例如从1号公交车站到2号公交车站，从2号公交站到3号或7号公交车站等等
我试图遍历这个图结构，并从给定的起点找到所有长度大于1的可能路径。例如，对于1的起点，所有可能路径的列表将是
[[1,2] , [1,2,3] , [1,2,3,4] , [1,2,7] , [1,2,7,8], [1,2,7,4]]
我试图递归地解决这个问题，迭代当前键的子项(该键的值(，并调用一个函数，该函数本质上扩展了该键的子级。这是我到目前为止的代码：
if hash.has_key?(origin.to_s)
tmp = origin.to_s
tmp << hash[origin.to_s][0]
paths.push(tmp)
expand_node(hash,paths,paths.length-1,tmp[tmp.length-1])
end
原点是起点。首先，我将第一个路径(在本例中为[1,2](添加到一个名为paths的数组中，然后扩展添加到前一个路径(本例中是2(的最后一个值。
def expand_node(hash,paths,curr_paths_index,node)
curr_node = node
if hash.has_key?(node.to_s)
counter = 0
hash[curr_node].each do |child|
tmp = paths[curr_paths_index]
tmp << child
paths << tmp
curr_paths_index += counter + 1
puts paths
expand_node(hash,paths,curr_paths_index,child)
end
end
结束
参数curr_paths_index跟踪我展开的路径。参数path是当前找到的全部路径列表。参数node是当前正在展开的值。
功能完成后打印paths产生：
123
123
1234
1234
1234
12347
12347
12347
12347
123478
123478
123478
123478
123478
1234784
1234784
1234784
1234784
1234784
1234784
是否有任何方法可以修改此代码，使其产生所需的输出(如上所示(？总的来说，有没有更好的方法来解决这个问题？
谢谢。
解决递归问题的一种方法是首先将其分解为一个易于解决的案例，然后将其推广到一个案例中。这里有一个更简单的例子：
给定一个图和通过该图的路径，确定哪些节点可以添加到该路径的末尾而不创建循环。
如果我们能解决这个问题，我们也可以很容易地解决更大的问题。
- 从一个仅作为起始节点的路径开始
- 查找可以添加到该路径而不创建循环的所有节点
- 对于每个这样的节点，输出一个路径，该路径是您的初始路径加上该节点，然后
- 使用新路径从步骤2开始递归重复
注意，如果在步骤2中没有找到新节点，递归调用将终止，因为步骤3和4没有任何作用。
以下是我将如何解决步骤2，我将把递归部分留给你
def find_next_nodes graph, path
graph[path[-1]].reject { |node| path.include? node }
end
我会这样做，很确定这可以进一步优化，而且可能还会出现性能问题。
require 'set'
dt = {"1"=>["2"], "2"=>["3", "7"], "3"=>["4"], "5"=>["6", "2"], "6"=>["7"], "7"=>["8", "4"]}
def traverse(initial_hash, key_arrays, traversed_keys = [])
value = []
key_arrays.map do |key|
n = [*traversed_keys, key]
value << n unless n.count == 1 # prevent first key to be added
another_keys = initial_hash.fetch(key, nil) # try to load the value, fallback to nil if key not found
if another_keys.nil? # stop condition
value << n
elsif another_keys.is_a?(Enumerable) # if key found
another_keys.map do |ank| # recursive
value.concat([*traverse(initial_hash, [ank], n)]) # splat operator to unpack the array
end
end
end
value.to_set # only return unique value, can be converted to array if needed
end
traverse(dt, [1].map(&:to_s)).map { |val| val.join('') }
很抱歉，但我还没有调试您的代码，所以我认为那里的临时变量有问题，因为无法再扩展的路径被转移到下一次迭代。
def doit(graph, start)
return [] unless graph.key?(start)
recurse(graph, start).drop(1)
end
def recurse(graph, start)
(graph[start] || []).each_with_object([[start]]) { |next_node, arr|
recurse(graph, next_node).each { |a| arr << [start, *a] } }
end
graph = { 1=>[2], 2=>[3, 7], 3=>[4], 5=>[6, 2], 6=>[7], 7=>[8, 4] }
doit(graph, 1)
#=> [[1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 7], [1, 2, 7, 8],
# [1, 2, 7, 4]]
doit(graph, 2)
#=> [[2, 3], [2, 3, 4], [2, 7], [2, 7, 8], [2, 7, 4]]
doit(graph, 3)
#=> [[3, 4]]
doit(graph, 5)
#=> [[5, 6], [5, 6, 7], [5, 6, 7, 8], [5, 6, 7, 4], [5, 2],
# [5, 2, 3], [5, 2, 3, 4], [5, 2, 7], [5, 2, 7, 8], [5, 2, 7, 4]]
doit(graph, 6)
#=> [[6, 7], [6, 7, 8], [6, 7, 4]]
doit(graph, 7)
#=> [[7, 8], [7, 4]]
doit(graph, 4)
#=> []
doit(graph, 99)
#=> []