代码之家 › 专栏 › 技术社区 › Abel

得到一个长度不等的列表的笛卡尔积,并对每个项应用一个函数('a->'b list)

f# recursion algorithm

Abel · 技术社区 · 7 年前

我已经挣扎了一段时间了。虽然我有一些长期的强制性方法,但我决定重新设计这部分:

列出每个子列表的第一个项目,然后再列出第一个项目,但是从最后一个子列表开始,第二个项目,然后是第三个项目,直到最后一个列表用完为止,对N-1子列表做同样的操作,基本上给出了所有这些列表的乘积

换句话说: [abc][FG][98] 应该像(应用函数)一样计算 f 对于每个项目,逗号表示可读性):[aF9,aF8,aG9,aG8,bF9,bF8,bG9,bG8,cF9,cF8,cG9,cG8]
将其展平并对结果的每个项应用一个函数,结果本身返回一个列表
当子列表为空(称为E)时,则只有子列表 0 .. E-1

let rec nestedApply f inp =
    match inp with
    | [] -> []
    | [x] -> x |> List.collect f
    | [x;y] -> 
        x
        |> List.collect (fun a -> y |> List.collect (fun b -> [a;b]))
        |> List.collect f
    | [x;y;z] -> 
        x
        |> List.collect (fun a -> y |> List.collect (fun b -> z |> List.collect (fun c -> [a;b;c])))
        |> List.collect f
    | head::tail ->
        // ??? I gave the following several attempts but couldn't get it right
        nestedApply f tail
        |> List.collect (fun a -> a::head)
        |> List.collect f

我更喜欢一个不会把事情搞砸的解决方案。最终,我将需要这个来懒散地评估,所以我可能求助于序列,但对于列表,我认为算法将是最容易考虑的。

例子: nestedApply (fun a -> [a]) [[1 .. 5];[6;7];[11;12]]

输出示例:

[1; 6; 11; 1; 6; 12; 1; 7; 11; 1; 7; 12; 2; 6; 11; 2; 6; 12; 2; 7; 11; 2; 7;
 12; 3; 6; 11; 3; 6; 12; 3; 7; 11; 3; 7; 12; 4; 6; 11; 4; 6; 12; 4; 7; 11; 4;
 7; 12; 5; 6; 11; 5; 6; 12; 5; 7; 11; 5; 7; 12]

另外,既然这看起来像是一个非常“正常”的算法,尽管它不是笛卡尔积,那么它最接近的典型的著名算法是什么?

2 回复 | 直到 7 年前

Abel 7 年前

您拥有的数据集称为 N-ary
在这里,每个节点/列表元素之间可能有若干子元素 0 <= children <= N .

算法步骤:

lists .
depth first search 添加到列表中的每个元素。
list .
新建一个空的 列表 在父级,将父元素添加到每个返回的子列表中,并将其添加到 列表
归还 列表 .

伪代码:

function possibleLists(curr_list){
  my_new_lists = [];
  for each element in curr_list:
     child_lists = possibleLists(element)
     for each child_list in child_lists:
         child_list.add(element)
         my_new_lists.add(child_list)    
     if child_lists.size() == 0: // needed if there were no further deep levels than the level of curr_list elements
         my_new_lists.add(new List().add(child_list)) // you can return current instance to have this kind of chaining.      

  return my_new_lists;
}

注: 如果要实现尾部递归,则必须将访问的元素的路径作为 列表 添加到它的子元素中。

F# 编码器,所以可以帮助你的伪代码在最大限度。

Abel 7 年前

感谢@vivekè23为N元树提供了指针,我读了一些关于树遍历之类的文章,这不完全是关于这个的(如果我错了,请纠正我),但它让我找到了一个简单的,而且我相信很优雅的解决方案:

let rec nestedApply f acc inp =
    match inp with
    | [] -> f acc
    | head::tail -> 
        [
            for x in head do
                yield! nestedApply f (x::acc) tail
        ]

在这种情况下,apply函数 f 对每个迭代都具有相同长度的小子列表执行操作,但对于我的特殊情况,这并不重要(而且,如果apply函数不需要关心子列表的顺序,它会加快速度)。要获得与原始问题完全相同的行为,请如下使用:

> nestedApply List.rev [] [[1 .. 5];[6;7];[11;12]];;
val it : int list =
  [1; 6; 11; 1; 6; 12; 1; 7; 11; 1; 7; 12; 2; 6; 11; 2; 6; 12; 2; 7; 11; 2; 7;
   12; 3; 6; 11; 3; 6; 12; 3; 7; 11; 3; 7; 12; 4; 6; 11; 4; 6; 12; 4; 7; 11; 4;
   7; 12; 5; 6; 11; 5; 6; 12; 5; 7; 11; 5; 7; 12]

稍微整洁的溶液会隐藏蓄能器:

let nestedApply f inp =
    let rec innerLoop acc inp =
        match inp with
        | [] -> f acc
        | head::tail -> 
            [
                for x in head do
                    yield! innerLoop (x::acc) tail
            ]

    innerLoop [] inp