분할

최근 누군가 “pluscal 퍼즐”에 대해 물어 왔다:

집합 S의 모든 분할(partition)을 생성하는 연산자(operator)가 필요하다. S는 상수/모델 변수다.

각 Partition은 Part들의 집합이며(각 Part 또한 집합이다), 다음을 만족한다:
/\ Part \in SUBSET S
/\ \A part1, part2 \in Partition:
  part1 # part2 => part1 \intersect part2 = {}
/\ UNION Partition = S

다시 말해:

Partitions(3) =
{
  { {1,2,3} },
  { {1,2}, {3} },
  { {1,3}, {2} },
  { {1}, {2,3} },
  { {1}, {2}, {3} }
}

이 연산자를 구현해 보자. 좀 더 일반적으로 만들기 위해, 여기서는 Partitions가 숫자 대신 값의 집합을 받는다고 하겠다.

연산자

먼저 원소가 집합의 집합이 아니라 집합의 시퀀스(sequence)라고 잠깐 상상해 보자. 즉 원소가 { {a,c}, {b} }가 아니라 << {a, c}, {b} >>인 것이다. 이제 같은 정보를 a :> 1 @@ b :> 2 @@ c :> 1로도 인코딩할 수 있다는 점에 주목하자: “a”는 첫 번째 집합에, “b”는 두 번째 집합에 있다는 식이다.

그리고 이건 그냥 함수 집합(function set) [{a, b, c} -> 1..3]에 속한 함수 하나일 뿐이다! 그 집합의 모든 함수는 각 값과, 분할에서 그 값이 속한 집합 사이의 매핑으로 읽을 수 있다. 필요한 것은 반대 방향으로 가는 연산자, 즉 “값에서 인덱스로의 맵”을 “인덱스에서 값 집합으로의 맵”으로 바꾸는 연산자뿐이다.

EXTENDS Integers, TLC, Sequences, FiniteSets

PartitionsV1(set) ==
  LET F == [set -> 1..Cardinality(set)]
    G(f) == [i \in 1..Cardinality(set) |-> {x \in set: f[x] = i}]
  IN
    {G(f): f \in F}

>> PartitionsV1({"a", "b"})
{<<{}, {"a", "b"}>>, <<{"a"}, {"b"}>>, <<{"b"}, {"a"}>>, <<{"a", "b"}, {}>>}

이제 이걸 다시 집합으로 바꾸기만 하면 된다. 이 작업은 집합 맵(set map)과 Range 헬퍼로 할 수 있다. Range를 <<{1, 2}, {}>>에 적용하면 집합 {{1, 2}, {}}가 나온다는 점에 유의하자. 그래서 차집합으로 공집합을 빼 줘야 한다.

Range(f) == {f[x] : x \in DOMAIN f}

Partitions(set) ==
    {Range(P) \ {{}}: P \in PartitionsV1(set)}

성능 노트

이 연산자는 분할 중 상당수가 중복이라 꽤 비효율적이다: <<{1, 2}, {}>>는 <<{}, {1, 2}>>와 같은 분할이다. [1..n -> 1..n]의 원소는 n^n개이므로,1 1..4에 대한 함수 집합은 원소가 256개인 반면 가능한 분할은 15개뿐이다. 10배가 넘는 오버헤드다!

하지만 이 경우에는 오버헤드가 그리 중요하지 않다고 본다. 분할의 집합을 생성하려는 주된 이유는 각 분할을 스펙의 서로 다른 구성으로 쓰기 위해서인데, 그렇다면 원소 256개짜리 집합을 계산하는 비용은 상태 공간(state space)을 15배로 불리는 비용에 묻혀 버린다.

(집합의 분할 개수는 벨 수를 따른다.)

1: 때로는 n^n을 “테트레이션(tetration)”이라고 부르고 ²n으로 쓰기도 한다. 이 표기법에서 ³n은 n^(n^n)이다.