非交和
非交和(disjoint union)
共通な元を持たない
$ A \sqcup B = A \cup^* B = \{ A \times \{ 0 \} \cup B \times \{1\}\} = A^* \cup B^*
直積は集合と集合を掛けて組(ペア)を作る操作
{1, 2} × {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4)}
集合の非交和は$ \sqcup 、または$ \cup^* と書かれるらしい
$ \sqcup : \sqcup、⊔
$ \cup^* : \cup^*
例:
$ A = \{ 1, 2, 3 \},\ B = \{ 1, 2 \}
$ A \sqcup B
$ = A \cup^* B
$ = \{ A \times \{0\} \cup B \times \{ 1 \} \}
$ = \{ \{ (1,0), (2, 0), (3, 0) \} \cup \{ (1, 1), (2, 1) \} \}
$ = \{ (1, 0), (2, 0), (3, 0), (1, 1), (2, 1) \}
より一般的な定義
$ \bigsqcup_{i \in I} A_i = \bigcup_{i \in I}\lbrace (x, i) | x \in A_i \rbrace
code:memo.hs
disjoint_union a b = zip a (take (length a) $ repeat 0) ++ zip b (take (length b) $ repeat 1)
main :: IO ()
main = do
print $ disjoint_union ax bx
より一般的の方で実装すると↓になった。
code:memo.hs
disjoint_union a = f a 0
where
f [] _ = []
f a i =
zip (head a) (take (length $ head a) $ repeat i)
++ f (tail a) (i + 1)
main :: IO ()
main = do
let
print $ disjoint_union a, b Pythonで実装したバージョン
code:disjoint_union.py
import collections
import itertools
def take(n, iterable):
return list(itertools.islice(iterable, n))
zip(ax, take(len(ax), 0 * len(ax))) + zip(ax, take(len(bx), 1 * len(bx))) (要動作確認)
C言語でも実装してみた。恐ろしく時間がかかった。Wolfram MathWorldの方の定義で精一杯。 code:disjoint_union1.c
/**
* 非交和を計算する
* A ⊔ B = {1, 2, 3} ⊔ {1, 2}
* = {{1, 0}, {2, 0}, {3, 0}, {1, 1}, {2, 1}}
*/
void disjoint_union1(int *a, size_t a_size, int *b, size_t b_size, int **out) {
for (unsigned int a_i = 0; a_i < a_size; a_i++) {
}
for (unsigned int b_i = 0; b_i < b_size; b_i++) {
}
}
char * join_strings(const char **strings, size_t count) {
// 必要な合計長を計算（カンマとヌル文字の分も加える）
// ヌル終端文字のために初期値は1にする
size_t totalLength = 1;
for (unsigned int i = 0; i < count; i++) {
totalLength += strlen(stringsi) + (i < (count - 1) ? 1 : 0); }
// 結果となる文字列用のメモリを確保
char *result = malloc(totalLength);
if (result == NULL) {
// メモリ確保失敗
return NULL;
}
// 空の文字列で初期化
// 文字列の結合
for (unsigned int i = 0; i < count; i++) {
strcat(result, stringsi); if (i < (count - 1)) {
strcat(result, ",");
}
}
return result;
}
int main() {
int a[] = {1, 2, 3};
int b[] = {1, 2};
size_t a_size = sizeof(a) / sizeof(a0); size_t b_size = sizeof(b) / sizeof(b0); size_t ab_size = a_size + b_size;
int **arr = (int **)malloc(sizeof(int *) * ab_size);
for(unsigned int i = 0; i < ab_size; i++) {
arri = (int *)malloc(sizeof(int) * 2); }
disjoint_union1(a, a_size, b, b_size, arr);
for (unsigned int i = 0; i < ab_size; i++) {
char *str = malloc(20);
}
char *joinedString = join_strings((const char **)strArray, ab_size);
if (joinedString != NULL) {
printf("%s\n", joinedString); free(joinedString);
}
}
code:memo
参考
C言語実装
メモ
関連