使用递归可能在元素列表中的位置？

Question

任何人都可以告诉如何在列表中的不同位置插入一个元素，并使用only recursion作为列表返回这些可能的组合的列表？

例如，列表是(2 3)，要插入的元素是1。

输出：

list(
    list (1 2 3) 
    list (2 1 3) 
    list (2 3 1) 
) 

Answer 1

的第一步是确定输出应该是什么样子，在这种情况下，它应该是列表的列表。
第二步通常是将问题分解成输入列表的情况。

空单的情况下是很简单 - 结果是包含一个单列表

(define (insert i ls) 
    (if (null? ls) 
     (list (list i)) 
     (...))) 

对于非空列表的情况下的列表，它有助于检查预期的结构结果。

(insert 1 '(2 3)) 
--> 
((1 2 3) (2 1 3) (2 3 1)) 

请注意，只有结果的第一个元素1作为它的第一个元素，我们可以很容易地(cons 1 '(2 3))创建此。
其他元素都有输入列表的第一个元素作为它们的第一个元素，如果你看他们的尾部，你会看到它们是递归结果(insert 1 '(3))。
缺少的是你需要cons2后面的每一个。

现在我们拥有所有必要的部件 - 总之

(define (insert i ls) 
    (if (null? ls) 
     (list (list i)) 
     (cons (cons i ls) (<...something...> (insert i (cdr ls)))))) 

在那里我已经留下了“< ...什么...>”部分你要弄清楚。