재귀를 사용하여 목록의 서브셋

주어진 목록의 가능한 모든 하위 집합을 생성하는 함수를 작성해야합니다. 나는지도를 사용해야한다고 생각하지만, 반복을위한 올바른 구문을 고안하기 위해 애 쓰고있다. 아무 곳에 나 람다 문을 삽입해야합니까? (list 1 2 3)의재귀를 사용하여 목록의 서브셋

가능한 모든 부분 집합은 다음과 같아야 중 각 항목을 포함 또는 포함하지하여 파워 셋을 생성

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

출처

2013-10-17 user2888512

가능한 [메모리 효율적인 전력 집합 알고리즘] (http://stackoverflow.com/questions/7371264)/memory-efficient-power-set-algorithm) 링크 된 게시물에는 스키마 구현이 있습니다 –

감사합니다. 파워 세트 알고리즘 질문에 대한 답변을 살펴보면 정말 도움이되었습니다. – user2888512

생각한다. 기본 케이스는 항목이없는 경우이며,이 경우 전원 세트는 빈 세트가있는 세트입니다. 의사 코드는 다음과 같습니다

Powerset([]) = [[]] 
Powerset(first:rest) = 
    let subPowersets = Powerset(rest) in 
     [subPowerset for subPowerset in subPowersets] ++ 
     [first:subPowerset for subPowerset in subPowersets]

출처

2013-10-17 00:51:02 Claudiu

감사합니다. 나는 지금 기능을 설정하는 방법에 대해 알아. – user2888512

당신은 또한 시도 할 수 있습니다 : 나는 대신에 같은 (설정 조합)과 같은 다른 기능이 코드를 사용하지만

(define power-set 
(lambda (set) 
    (if (empty? set) '() 
     (remove-duplicates (append* (power-set (car set)) 
              (map (lambda (x) (cons (car A) x)) (power-set (cdr A))))))))

는 (제거 - 중복 (추가 *. ..)) 또한, 다른 함수를 사용하여 카디널리티에 맞게 정렬합니다.

수학적 정의를 읽으면 이러한 간단한 프로그램을 구성 할 수 있습니다. 설명서를 읽음으로써 향상시킬 수 있습니다 (일부 수학적 정의는 '재발'이 좋지 않지만 'tail-recursion'을 사용해보십시오)

출처

2013-10-17 17:40:26

재귀를 사용하여 목록의 서브셋

답변

관련 문제