주어진 목록의 파티션을 어떻게 찾을 수 있습니까?

Question

어떻게 정수 목록의 모든 파티션을 찾을 수 있습니까? 대부분 나는 SML로 구현할 때 재귀를 사용하는 알고리즘이 필요하다. 그냥 알고리즘이 필요합니다, 나는 혼자서 코딩 부분을 할 것입니다. 실수로 내가 하위 집합을 찾는 코드를 썼는데이 시간이 너무 남았습니다.

SML은 비슷한 파스칼이므로 형식이 잘못되었습니다. 나는 factorial로 작성하려고합니다. 예를 들어 재미 있습니다. fuc x = 만약 다른 0 후 0 < X의 경우, X = 다른 한 후 1 X * FAC (X-1) 미리

감사

Answer 1

The partition problem (그래서 대한 공지 다항식 공지 NP-Hard 문제가되지), 재귀를 사용하여 멋지게 작성된 철저한 검색을 사용하여 해결할 수 있습니다.

의사 코드 (이 도움이 분명 희망, ML-같은 의사 코드를하려고 노력) : 내가 제대로 e :: A은 ML에서 A의 시작 부분에 요소를 추가하고 기억한다면 (

partition([],A,B): #base clause 
    if (sum(A) == sum(B)): 
     print (A,B) # this is a partition 
partition(list, A,B): 
    e <- head(list) 
    partition(tail(list),e :: A,B) 
    partition(tail(list),A, e :: B) 

느낌 내가 잘못 생각하면 그것을 바로 잡을 수있다.)

Answer 2

이것을 확인하십시오 finding all the subsets. 기본적으로 각 순열 반복에서 현재 부분 집합의 합집합에서 전체 집합을 뺀 파티션의 다른 부분을 얻을 수 있습니다. 당신이 세트 S{S1,...,Sn}의 K-파티션이 {P1,...,Pk}을 말한다면

Answer 3

, 당신은 S ⋃ {Sn+1}의 k K-파티션을 생성 할 수 있습니다 : {1 ... K}에 i에 대한

{P1,..., Pi-1, Pi ⋃ {n+1}, Pi+1,... Pk}을

플러스 (k + 1) 파티션 P ⋃ {k+1}

생성 된 파티션을 P에서 호출하십시오. {1,...,n}의 두 개의 다른 파티션에서 생성 된 모든 파티션 세트가 분리되어 있고 {1,...,n+1}의 모든 파티션이 {1,...,n}의 일부 파티션에서 생성된다는 것을 쉽게 증명할 수 있습니다.

필자는 문제에 대한 재귀 적 해결책이 충분하다고 생각합니다. 검증을 위해

의 파티션 수의 수는 {1, ..., n을} 당신은 B이 미트에 대한 응답으로 판단 벨 번호 (슬론 A000110)

Answer 4

을 인 B(n)입니다

fun partitions [] = [] 
    | partitions [x] = [[[x]]] 
    | partitions (x::xs) = 
    let 
     val zsss = partitions xs 
    in 
     map (fn zss => [x]::zss) zsss @ 
     map (fn zs::zss => (x::zs)::zss) zsss 
    end 

편집가 : 찾고있는 것 같다 미안 해요, 즉, partition [1,2,3] = [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[1],[2],[3]]]로 이전 예를 오해, 파티션을 명령했다. 여기

은 (내가 생각하는) 실제 질문에 대한 솔루션입니다 :

fun extensions x [] = [] 
    | extensions x (xs::xss) = 
    ((x::xs)::xss) :: map (fn zss => xs::zss) (extensions x xss) 

fun partitions [] = [[]] 
    | partitions (x::xs) = 
    List.concat (map (fn zss => ([x]::zss) :: extensions x zss) (partitions xs))