再帰を使用してリスト内の要素の位置を指定できますか？

Question

リスト内の要素を異なる位置に挿入し、リストとして可能な組み合わせのリストをonly recursionを使って返す方法は誰にでも分かりますか？

たとえば、リストは(2 3)、挿入する要素は1です。

出力：

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

Answer 1

最初のステップは、出力がどのように見えるかを決定することであり、この場合には、それはリストのリストでなければなりません。
2番目の手順は、通常、問題を入力リストのケースに分割することです。

空のリストの場合は非常に簡単です - 結果は非空のリストの場合には1つのシングルトンリスト

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

を含むリストである、それは予想の構造を検討すると便利です結果。結果の最初の要素だけが、その最初の要素として1を持っている、と私たちは簡単に(cons 1 '(2 3))でこれを作成することができます

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

注意。
他の要素はすべて入力リストの最初の要素を最初の要素とし、末尾に(1 3)と(3 1)を見ると、それらが再帰の結果であることがわかります(insert 1 '(3))。
欠けているものは、後でcons2にする必要があるということです。要約

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

であなたが把握するために、私は「< ...何か...>」の部分を残してきた -

は、今、私たちは、すべての必要な部分を持っています。