순열을 사용하여 재귀를 사용하여

Question

나는 Scheme에서 순열을 만드는 다음 코드 조각을 발견했습니다.

(define (remove x lst) 
    (cond 
    ((null? lst) '()) 
    ((= x (car lst))(remove x (cdr lst))) 
    (else (cons (car lst) (remove x (cdr lst)))))) 

(define (permute lst) 
    (cond 
    ((= (length lst) 1)(list lst)) 
    (else (apply append(map(lambda (i) (map (lambda (j)(cons i j)) 
              (permute (remove i lst))))lst))))) 

첫 번째 함수의 제거, 단지를 없애는 것이 간단한 것 : 나는 주장처럼 입력하면 I (1 2 3)이 나에게 줄 것 '을 의미 :은 다음

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

코드입니다 x에 의해 표시된 caracter의리스트는리스트의 시작 부분과 비교하고 나머지 부분과 함께 재귀 적으로 호출함으로써 반복된다.

내가 얻지 못하는 부분은 permute 함수입니다. 내가 아는 한 map은 인수 (이 경우 목록)의 모든 요소에 함수를 적용하고 apply는 한 인수를 모든 인수에 완전히 적용합니다. 그래서 정확히이 라인 무엇을하고 있는지 : i와 j를, 우리가 걸릴 경우 그들은 (순열 요소와 목록해질 것이다 : 나를 위해

(apply append(map(lambda (i) (map (lambda (j)(cons i j)) 
               (permute (remove i lst))))lst))))) 

을 두 요소 쌍을 만들려고 것 같다 리스트는 단지 한 묶음의 연결 쌍임). 그러나 다시 말하자면, 나는 그 부분이 무엇을하고 있는가? 요소의 수가 없어 질 때까지 고정 된 요소 i의 쌍을 갖는 목록의 하위 집합을 생성하기 위해 목록의 헤드를 제거하는 것일뿐입니다.

어떤 도움이 필요합니까?

감사

Answer 1

나는 항상 쉽게 구현에 다이빙을하기 전에 더 높은 수준에서 알고리즘을 이해하고 거기에 무슨 일이 일어나고 있는지 을 이해하려고 노력하는 것으로 나타났습니다. 질문은 다음과 같습니다 : 목록의 순열은 무엇이며 어떻게 찾을 수 있습니까?

단일 요소 목록의 순열은 분명히 목록 일뿐입니다.

(a b)의 순열은 [(a b) (b a)]입니다. (a b c)의

순열은 일반적

[(a b c) (a c b) (b c a) (b a c) (c a b) (c b a)]

는 N있다 세트에게있다! (n-1) 개의 선택을 두 번째 요소에 대해 , 세 번째 요소에 대해 (n-2), 그리고 두 번째 요소에 대해 에. 이 의 자유도가 감소함에 따라 목록의 첫 번째 요소가 점점 더 암시됩니다. 은 목록의 순열에 따라 길이 n 목록의 순열을 나타낼 수 있습니다. 길이 (n - 1), 그리고 우리가 단일 요소 목록의 순열에이를 때까지 계속됩니다.

목록의 순열은 정확히 [목록의 각 요소에 대해 list \ element의 순열에 덧붙여지는 요소]라고 밝혀졌습니다.(a b c) 경우를 보면

는

이 사실임을 확인 - 우리는 a 등등 (a c) 및 (c a) 및 이전 (b c) 및 (c b), (b c)의 순열이고, b 앞에 있습니다. 하위 목록에 요소를 붙이는이 작업은

(define (prepend j) 
    (cons element j)) 

로 정의 될 수 있고 하위 목록의 모든 순열을 위해 그 일의 작업은 다음 (map prepend (permute sublist))이 될 것입니다. 이제는 각 요소에 대해 새로운 prepend 함수를 정의하면 이 과도 함일 수 있습니다. 특히 모든 요소가 동일한 양식을 가지고 있기 때문입니다. 그래서 더 나은 방법은 람다를 사용하는 것입니다. 람다는 고려중인 요소 인 의 값을 캡처합니다. 원하는 작업은 이고 (map (lambda (j) (cons element j)) (permute sublist))입니다. 이제, 우리는주고, 그렇게 다른지도를 사용 에 목록의 각 요소, 그리고 그 길에이 작업을 적용 할 : 이제

(map (lambda (element) 
     (lambda (j) (cons element j) (permute sublist))) 
    list) 

가이 좋아 보인다,하지만 문제가있다 : 각을 재귀 단계에는 단일 요소 이 사용되며 목록으로 바뀝니다. 길이가 1 인 목록은 괜찮습니다. 그러나 긴 목록의 경우 모든 재귀 호출에 대해 반복되므로 중첩 목록을 얻을 수 있습니다. 우리가 실제로하고 싶은 일은 을 모두 같은 발 밑에 두는 것입니다. 정확히 (apply append ...)이 처리하는 것입니다. 그리고 그게 거의 전부입니다. 유일한 것만 누락되면 하위 목록이 처음 생성되는 방식입니다. 그러나 도 간단합니다. remove을 사용하므로 sublist = (remove element list)이됩니다. 모든 것을 함께 퍼팅, 우리는

(apply append (map (lambda (i) 
         (lambda (j) (cons i j)) 
         (permute (remove i lst))) 
        lst)) 

기본 케이스 길이 = 1 사건을 담당하고, 다른 사람들이 모두 밖으로 안쪽에서 가고,의 떨어져이 직접 선택

Answer 2

거기에서 찾을 수 있습니다 . lst을 수정하고 해당 요소 중 하나에 내부 표현식을 적용하십시오.

> (define lst '(1 2 3)) 
> (define i 1) 
> (permute (remove i lst)) 
((2 3) (3 2)) 

좋아요. 내부 표현식은 요소를 제거하고 나머지 요소의 순열을 재귀 적으로 생성합니다. 이제 map이 순열을 통해 lambda :

> (map (lambda (j) (cons i j)) (permute (remove i lst))) 
((1 2 3) (1 3 2)) 

그래서 내부 map 우리가 여기 1에 설정 한 일부 i,로 시작하는 모든 순열을 생성합니다.

바깥 쪽 map은 lst의 모든 요소를 ​​첫 번째 요소로 고려하여 모든 순열을 생성합니다.

> (map (lambda (i) (map (lambda (j) (cons i j)) 
>      (permute (remove i lst)))) 
>  lst) 
(((1 2 3) (1 3 2)) ((2 1 3) (2 3 1)) ((3 1 2) (3 2 1))) 

그러나 너무 많은 중첩 목록이 생성됩니다. append을 적용하면

> (append '(1 2) '(3 4) '(5 6)) 
(1 2 3 4 5 6) 
> (apply append '((1 2) (3 4) (5 6))) 
(1 2 3 4 5 6) 

그래서 우리는 순열의 단순 목록을 얻을, 목록의 목록을 평평하게.