查找带可变轮的机械里程表的所有可能读数

Question

问题可以描述为找到机械里程表的所有可能读数,但需要注意的是它的车轮可能有不同数量的数字.

odometer = [["a1","a2","a3"],["b1","b2"],["c1","c2","c3","c4"]]

到目前为止我得到了什么:

read_heads :: [[[Char]]] -> [[Char]]
read_heads [[[]]] = [[]]
read_heads x = map head x

-- pushes the first element of a list to the end
rotate :: [a] -> [a]
rotate [] = []
rotate (x:xs) = xs ++ [x]

http://www.cartell.ie/car_check/wp-content/uploads/2010/02/Odometer-1.jpg

编辑:澄清问题.鉴于上面的里程表,创建一个包含所有可能读数的列表.

["a1","b1","c1"]
["a1","b1","c2"]
["a1","b1","c3"]
["a1","b1","c4"]
["a1","b2","c1"]
["a1","b2","c2"]
["a1","b2","c3"]
["a1","b2","c4"]
etc.

Answer 1

这可能是最简单的一个:

Prelude> let odometer a = sequence a
Prelude> odometer [["a1","a2","a3"],["b1","b2"],["c1","c2","c3","c4"]]
[["a1","b1","c1"],["a1","b1","c2"],["a1","b1","c3"],["a1","b1","c4"],["a1","b2","c1"],
["a1","b2","c2"],["a1","b2","c3"],["a1","b2","c4"],["a2","b1","c1"],["a2","b1","c2"],
["a2","b1","c3"],["a2","b1","c4"],["a2","b2","c1"],["a2","b2","c2"],["a2","b2","c3"],
["a2","b2","c4"],["a3","b1","c1"],["a3","b1","c2"],["a3","b1","c3"],["a3","b1","c4"],
["a3","b2","c1"],["a3","b2","c2"],["a3","b2","c3"],["a3","b2","c4"]]
Prelude>

sequence是一个处理monad的函数.如果你想使用Haskell,你需要理解monad,所以也可以从现在开始.

如果你还没有准备好让强大的monad进入你的生活,那么这是一个更平凡的版本:

Prelude> :{
Prelude| let odometer (xs:yys) = [x:ys | x<-xs, ys<-odometer yys]
Prelude|     odometer [] = [[]]
Prelude| :}
Prelude> odometer [["a1","a2","a3"],["b1","b2"],["c1","c2","c3","c4"]]
[["a1","b1","c1"],["a1","b1","c2"],["a1","b1","c3"],["a1","b1","c4"],["a1","b2","c1"],
["a1","b2","c2"],["a1","b2","c3"],["a1","b2","c4"],["a2","b1","c1"],["a2","b1","c2"],
["a2","b1","c3"],["a2","b1","c4"],["a2","b2","c1"],["a2","b2","c2"],["a2","b2","c3"],
["a2","b2","c4"],["a3","b1","c1"],["a3","b1","c2"],["a3","b1","c3"],["a3","b1","c4"],
["a3","b2","c1"],["a3","b2","c2"],["a3","b2","c3"],["a3","b2","c4"]]
Prelude>

它完全符合它在锡上的说法:

• 给出一个里程表轮子列表 (xs:yys)
• 所有可能的读数的列表的所有可能组合的名单X和YS = [ x:ys
• 这样的 |
• x取自第一轮的所有可能位置的列表x<-xs
• 和 ,
• ys取自从其余车轮构造的里程表的所有可能读数列表(即除了第一个车轮之外的所有读数) ys<-odometer yys].
• 如果里程表没有轮子 []
• 只有一个可能的读数,这是空的 = [[]]