时间戳

首页 > 解决方案 > 如果子列表检查失败，列表理解停止生成某些列表

erlang - 如果子列表检查失败，列表理解停止生成某些列表

问题描述

我有一个代码，它通过重复生成所有可能的变化（长度为 N）。

variation(1, L) ->
    [ [H] || H <- L ];
variation(N, L) ->
    [[H | T] || H <- L, T <- variation(N - 1, L)].

对于variation(3, [1,2,3,4])，它将生成：

[[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,1,4],[1,1,2,1] ……]

我想在列表生成过程中检查一个条件。如果子列表失败，它应该停止生成从某个子列表开始的列表。例如，如果 [1,1] 子列表未能满足该条件（检查），则它不应生成 [1,1,1,1]、[1,1,1,2] 等（所有以 [1 ,1])。

我不知道它是否可能与 1 列表理解。到目前为止，我有这个代码：

variation(1, L) ->
    [ [H] || H <- L ];
variation(N, L) ->
    [[H | T] || H <- L, T <- variation(N - 1, L), check([H|T]) ].

这个解决方案只会返回那些不会失败的列表（它有效，但对于大输入来说真的很慢）。

如果 [1,1] 失败，它将尝试生成 [1,1,1,2]，但这些也会导致检查失败。我需要一个解决方案，它不会尝试生成以 [1,1,...] 开头的列表（或以前失败的子列表）。

标签： erlang

解决方案

首先是一个小细节：根据您的问题，variations(3, [1,2,3]).应该生成[[1,1,1,1], [1,1,1,2], …]但它实际上会生成[[1,1,1], [1,1,2], …]. 我会假设代码是正确的，你的意思是说variations(4, [1,2,3]).应该生成[[1,1,1,1], [1,1,1,2], …]

我编写了您的函数的另一个版本，在 LC 右侧使用不同的顺序，避免在使用以下命令检查其前缀已经为假时生成列表check/1：

variation(1, L) ->
    [ [Elem] || Elem <- L ];
variation(N, L) ->
    [ Init ++ [Last] || Init <- variation(N-1, L), check(Init), Last <- L].

如您所见，因为check(Init)发生在 之前 Last <- L，Last仅在 时生成check(Init) == true。这可能会产生您想要的效果。

不过要小心。我++在 LC 的左侧使用。您绝对应该对代码进行基准测试，看看这是否对性能有影响。

如果确实如此，并且仅当确实如此，您可能需要考虑使用以下内容：

variation3(1, L) ->
    [ [Elem] || Elem <- L ];
variation3(N, L) ->
    [ lists:reverse([Last|lists:reverse(Init)]) || Init <- variation2(N-1, L), check(Init), Last <- L].

也许值得，也许不……你需要对你的东西进行基准测试才能弄清楚。

推荐阅读