위키득계정 ↗
과학

다중집합

다중집합과학
영어
Multiset
순서
구분하지 않음
반복
원소별 횟수를 구분
표현
원소별 중복도를 기록
다중집합은 원소의 순서는 구분하지 않지만 각 원소가 나타나는 횟수는 구분하는 집합과 비슷한 대상이다. 보통의 집합과 달리 같은 원소를 여러 번 포함할 수 있으며, 그 횟수를 중복도라고 한다.

집합과 다른 점

보통의 집합에서는 같은 원소를 반복해서 적어도 포함 여부만 의미가 있다. 다중집합에서는 {a,a,b}와 {a,b}가 다르다. 첫 번째에는 a가 두 번 있고 두 번째에는 한 번 있기 때문이다. 반면 {a,a,b}와 {b,a,a}는 원소별 횟수가 같으므로 같은 다중집합이다.

중복도로 나타내기

각 원소 x에 대해 나타나는 횟수 m(x)를 기록하면 나열 순서와 무관하게 다중집합을 나타낼 수 있다. 유한한 다중집합 {a,a,b,c,c,c}에서는 a의 중복도가 2, b는 1, c는 3이다. 포함되지 않은 원소의 중복도는 0으로 두며 중복도를 합하면 전체 원소 수 6을 얻는다.

문자열과 빈도 구분

문자열 aab와 aba는 순서가 달라 서로 다른 문자열이지만 원소 빈도만 보면 같은 다중집합이다. 따라서 문자열을 문자 빈도로 바꾸는 것은 순서 정보를 버리는 변환이다. 원소별 개수만 필요한 문제에는 적합하지만 원래 순서를 복원해야 하는 문제에는 정보가 충분하지 않다.

중복 선택 문제와 연결

서로 다른 원소 종류 중 같은 종류를 반복해 선택하고 선택 순서를 구분하지 않으면 결과를 다중집합으로 볼 수 있다. 이는 중복조합의 기본 해석이다. 반대로 각 종류를 사용할 수 있는 최대 횟수가 정해져 있으면 무제한 반복 선택과 다른 조건의 문제가 된다.

관련 문서

집합 / 중복조합 / 문자열 / 순열 / 조합 / 정수 분할