时间戳

首页 > 解决方案 > 带有子列表的方案/球拍插入无处不在的功能

functional-programming - 带有子列表的方案/球拍插入无处不在的功能

问题描述

所以我一直在尝试解决这个问题：

给定一个元素 E 和一个列表 L 将 E 插入到列表 L 的每个位置（因此结果是一个列表列表）。示例： (insert-everywhere 'a '(b c))会给((a b c) (b a c) (b c a))

这很容易，但我的问题中还有另一个条件让我很难 - 如果 L 的元素本身是一个列表，那么该元素也必须插入到子列表中的每个位置。例如：

(insert-everywhere 'd '(a (b c)))将返回：((d a (b c)) (a d (b c)) (a (d b c)) (a (b d c)) (a (b c d)) (a (b c) d))。

这是我到目前为止的代码（我主要是从这里提取的）：

#lang racket
(define (insert-at pos elmt lst) 
 (if (empty? lst) (list elmt)
 (if (list? (car lst)) (insert-everywhere elmt (car lst))
 (if (= 1 pos)
  (cons elmt lst)
  (cons (first lst) 
        (insert-at (- pos 1) elmt (rest lst)))))))

(define (insert-everywhere sym lst)
  (remove-duplicates
    (map (lambda (i)
      (insert-at i sym lst))
        (range 1 (+ 2 (length lst))))))

这行：(if (list? (car lst)) (insert-everywhere elmt (car lst))应该处理子列表，但它不起作用。（如果我(insert-everywhere 'd '(a (b c)))使用上面的代码运行，我会得到((d a (b c)) (a (d b c) (b d c) (b c d)))）

如果有人对如何以不同的方式处理这个问题有任何建议，我很乐意听到。

标签： functional-programmingschemeracket

解决方案

我不会做索引，因为它非常低效。而是反转输入列表并从头到尾构建列表，使结果以相反的顺序排列。您有一个当前列表，您可以向其中添加元素cons，您可以使用该列表向结果中添加新内容，并且每个存在的结果的每个级别也会添加一个元素。

作为参数，你有状态。当我提出参考时，我使用result并且cur通常我的迭代确实是这样的(insert-everywhere 'd '(a b c))：

lst     cur     results
(c b a) ()      ((d))
(b a)   (c)     ((d c) (c d))
(a)     (b c)   ((d b c) (b d c) (b c d))
()      (a b c) ((d a b c) (a d b c) (a b d c) (a b c d)))

现在添加对子列表的支持只是对它们做同样的事情，然后做一个映射，以便您在结果中为每个子列表创建一个结果，cur除了将其添加为元素之外还添加。

请注意，所有新结果都只是 cur 添加了一个插入的元素，并且所有 th erest 都在 fron 中获得了一个新元素，它是输入的第一个元素。cur将增长并共享，因此只有插入元素之前的元素对于该子结果是唯一的。

我有一个可行的实现，但过早地获得解决方案并不好玩。玩得开心。

推荐阅读