使用遞歸可能在元素列表中的位置？

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)))))) 

在那裏我已經留下了「< ...什麼...>」部分你要弄清楚。