Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@momeemt

Nimで "集合" を扱う sets

はじめに

こんにちは。高校2年の樅山です。

の記事となります。

他の標準ライブラリを調べる👇

sets

setsは、効率的に実装された集合である HashSet と、順序情報に基づいて要素を並べる集合 Order Set、その二つの集合の共用体である SomeSet を提供するNimの標準ライブラリの一つです。
ちなみに、単なる集合である set は、同じく標準ライブラリの一つである、systemによって提供されているので明示的な import をしなくても利用することができます。

setsをimportする
import sets

HashSet を使う

HashSetは、ハッシュ構造によって効率的に実装された集合です。

systemモジュールで定義されている set では、順序型クラスに属する型でなければいけないこと、最大要素数が 2^16 を超える可能性のある型の集合は扱えないことの2つの制限がありました。
しかし、HashSetではハッシュ化できるデータ型ならば無制限に扱うことができます。

配列をもとに HashSet を生成する

toHashSetopenArray1の配列を渡すことで、重複要素を削除した集合、HashSet型の値を返します。

HashSetを宣言する
import sets

var mySet: HashSet[int] = toHashSet([1, 2, 3, 4, 5, 5])
echo mySet

上のコードでは、{3, 4, 2, 5, 1}が出力されます。2

集合に要素を追加する

inclに、集合と要素を渡すことで、集合に要素を追加することができます。
渡す集合は、可変変数に格納されている必要があります。

要素を追加する
import sets

var mySet = toHashSet([1, 2, 3])
mySet.incl(4)

echo mySet

上のコードでは、{3, 4, 2, 1}が出力されます。

集合から要素を取り除く

exclに、集合と要素を渡すことで、集合から要素を取り除くことができます。
もし、集合にない要素を渡すと、exclは集合に対してなんの操作もしません。
渡す集合は、可変変数に格納されている必要があります。

要素を取り除く
import sets

var mySet = toHashSet([1, 2, 3, 4])
mySet.excl(2)

echo mySet

上のコードでは、{3, 4, 1}が出力されます。

二つの集合の和集合を取る

unionに、二つの集合を渡すことで和集合3を取ることができます。

和集合を取る
import sets

let
  set1 = toHashSet(["apple", "orange", "grape"])
  set2 = toHashSet(["banana", "lemon", "orange"])

echo set1.union(set2)

上のコードでは、{"apple", "banana", "orange", "lemon", "grape"}が出力されます。

ちなみに、より直感的な記法として +演算子がエイリアスとして用意されています。

+演算子を用いて和集合を取る
import sets

let
  set1 = toHashSet([1, 2, 3, 4, 5])
  set2 = toHashSet([2, 3, 4, 5, 6, 7])

echo set1 + set2

上のコードでは、{3, 4, 2, 6, 5, 7, 1}が出力されます。

また、前述のinclに、集合を2つ渡すことで和集合を取ることもできます。
渡す集合は、可変変数に格納されている必要があります。

inclを用いて和集合を取る
import sets

var
  set1 = toHashSet([3, 1, 4, 1, 5])
  set2 = toHashSet([2, 7, 1, 8, 2, 8])

set1.incl(set2)

echo set1

上のコードでは、{3, 4, 2, 5, 7, 8, 1}が出力されます。

二つの集合の差集合を取る

differenceに、二つの集合を渡すことで差集合4を取ることができます。

差集合を取る
import sets

let
  set1 = toHashSet([true, false])
  set2 = toHashSet([true])

echo set1.difference(set2)

上のコードでは、{false}が出力されます。

また、和集合と同様、より直感的な記法として、-演算子がエイリアスとして用意されています。

-演算子を用いて差集合を取る
import sets

let
  set1 = toHashSet([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  set2 = toHashSet([1, 4, 6, 8, 9, 10])

echo set1 - set2

上のコードでは、{5, 3, 2, 7}が出力されます。

加えて、前述のexclに、集合を2つ渡すことで差集合を取ることもできます。
渡す集合は、可変変数に格納されている必要があります。

exclを用いて差集合を取る
import sets

var
  set1 = toHashSet([2, 4, 6, 8, 10, 12, 14, 16])
  set2 = toHashSet([3, 6, 9, 12, 15])

set1.excl(set2)

echo set1

上のコードでは、{14, 16, 4, 2, 8, 10}が出力されます。

二つの集合の積集合を取る

intersectionに、二つの集合を渡すことで積集合5を取ることができます。

積集合を取る
import sets

let
  set1 = toHashSet([6, 12, 18, 24, 30, 36, 42, 48])
  set2 = toHashSet([4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48])

echo set1.intersection(set2)

上のコードでは、{12, 48, 24, 36}が出力されます。

また、同様に積集合にも*演算子という直感的なエイリアスが存在します。

*演算子を用いて積集合を取る
import sets

let
  set1 = toHashSet([3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42])
  set2 = toHashSet([7, 14, 21, 28, 35, 42, 49, 56])

echo set1 * set2

上のコードでは、{21, 42}が出力されます。

二つの集合の対称差を取る

symmetricDifferenceに、二つの集合を渡すことで対称差6を取ることができます。

対称差を取る
import sets

let
  set1 = toHashSet(["tokyo", "kyoto", "kanagawa", "osaka"])
  set2 = toHashSet(["kyoto", "shiga", "nara", "osaka"])

echo set1.symmetricDifference(set2)

上のコードでは、{"nara", "shiga", "kanagawa", "tokyo"}が出力されます。

また、同様に対称差にも-+-演算子というエイリアスが存在します。

-+-演算子を用いて対称差を取る
import sets

let
  set1 = toHashSet(['a', 'i', 'u', 'e', 'o'])
  set2 = toHashSet(['a', 'z', 'i', 'f', 'u', 'r', 'a', 'i'])

echo set1 -+- set2

上のコードでは、{'o', 'z', 'r', 'f', 'e'}が出力されます。

二つの集合が素集合であるかを確かめる

disjointに、二つの集合を渡すことで、素集合7であるかを確かめることができます。
素集合の場合は true を、素集合ではない場合は false を返します。

素集合であるかを確かめる
import sets

let
  set1 = toHashSet([1, 3, 5, 7, 9])
  set2 = toHashSet([0, 2, 4, 6, 8])

if set1.disjoint(set2):
  echo "yay!"
else:
  echo ":("

上のコードでは、yay!が出力されます。

集合にある要素が含まれているかどうかを確かめる

containsに、集合とある要素を渡すことで、集合に要素が含まれているかどうかを確かめることができます。
含まれている場合は true を、含まれていない場合は false を返します。

集合にある要素が含まれているかどうかを確かめる
import sets

var mySet = toHashSet([2, 3, 5, 7, 11, 13])

echo mySet.contains(2)

上のコードは、trueを出力します。

また、in演算子を用いることでも同様の結果を得られます。

in演算子を用いて集合にある要素が含まれているかどうかを確かめる
import sets

var mySet = toHashSet([2, 3, 5, 7, 11, 13])

echo 10 in mySet

上のコードは、falseを出力します。

集合にある要素が含まれていないかどうかを確かめる

missingOrExclに、集合とある要素を渡すことで、集合に要素が含まれていないかどうかを確かめることができます。
含まれていない場合は true を、含まれている場合は false を返します。

集合にある要素が含まれていないかどうかを確かめる
import sets

var mySet = toHashSet([2, 3, 5, 7, 11, 13])

echo mySet.missingOrExcl(2)

上のコードでは、falseが出力されます。

集合にある要素が含まれていなければ要素を追加する

containsOrInclに、集合とある要素を渡すことで、ある要素が含まれていれば true を返し、含まれていなければ、要素を追加した上で false を返します。
渡す集合は、可変変数に格納されている必要があります。

集合にある要素が含まれていなければ要素を追加する
import sets

var mySet = toHashSet([0, 2, 4, 6, 8, 10])

echo mySet.containsOrIncl(12)
echo mySet.containsOrIncl(0)

echo mySet

上のコードでは、

結果
false
true
{4, 2, 6, 8, 10, 0, 12}

を出力します。

集合Aが集合Bの部分集合かどうかを確かめる

<演算子を用いると、集合Aが集合Bの厳密な部分集合8かどうかを確かめることができます。

集合Aが集合Bの厳密な部分集合かどうかを確かめる
import sets

let
  set1 = toHashSet([1, 2, 3])
  set2 = toHashSet([1, 2, 3])

echo set1 < set2

上のコードでは、falseが出力されます。

また、<=演算子を用いると、集合Aが集合Bの部分集合9かどうかを確かめることができます。

集合Aが集合Bの部分集合かどうかを確かめる
import sets

let
  set1 = toHashSet([1, 2, 3])
  set2 = toHashSet([1, 2, 3])

echo set1 <= set2

上のコードでは、trueが出力されます。

二つの集合が等しいかを確かめる

==演算子を用いると、二つの集合が等しいかどうかを確かめることができます。

二つの集合が等しいかを確かめる
import sets

let
  set1 = toHashSet([1, 2, 3, 4])
  set2 = toHashSet([1, 3, 2, 4])

echo set1 == set2

上のコードでは、trueを出力します。

空集合に変換する

clearに、集合を渡すと空集合10に変換することができます。
渡す集合は、可変変数に格納されている必要があります。

空集合に変換する
import sets

var mySet = toHashSet([0, 2, 4, 6, 8, 10])
mySet.clear

echo mySet

上のコードでは、{}が出力されます。

集合の要素数を得る

lenに、集合を渡すことで、その集合の要素数を得ることができます。

集合の要素数を得る
import sets

var mySet = toHashSet([2, 0, 0, 3, 1, 0, 3, 0])

echo mySet.len

上のコードは、4を出力します。

また、エイリアスであるcardに渡すことでも、同様の結果を得ることができます。

cardに集合を渡す
import sets

var mySet = toHashSet(['m', 'o', 'm', 'e', 'e', 'm', 't'])

echo mySet.card

上のコードは、4を出力します。

ハッシュ値を得る

hashに、集合を渡すことで、その集合のハッシュ値を得ることができます。

ハッシュ値を得る
import sets

let mySet = toHashSet([12, 24, 36])

echo mySet.hash

上のコードでは、2795717031454747059を出力します。

mapを適用する

HashSetには、mapを適用することができます。
具体的には、ある集合とラムダ式を渡すと、ラムダ式で全ての要素が処理された新しい集合を返します。

要素を二乗する
import sets

let
  mySet = toHashSet([1, 2, 3, 4, 5])
  square = proc (x: int): int = x * x
  squareSet = mySet.map(square)

echo squareSet

上のコードでは、{4, 16, 1, 9, 25}が出力されます。

文字列にキャストする

$に、集合を渡すと、文字列にキャストすることができます。
ここまでに集合を直接 echo に渡すことができたのは、echo内部で $ が適用されていたからです。

ポップする

popに、集合を渡すと、任意の要素を取り除くことができます。
ただし、空集合を渡すと、KeyError例外が発生します。
渡す集合は、可変変数に格納されている必要があります。

ポップする
import sets

var mySet = toHashSet([1, 2, 3, 4, 5])

echo mySet.pop

上のコードでは、3が出力されます。

for文で要素を走査する

HashSetには、itemsというイテレータが定義されているため、for文で要素を走査することができます。

要素を走査する
import sets

var mySet = toHashSet([1, 2, 3, 4, 5])

for elem in mySet.items:
  echo elem

上のコードは、

結果
3
4
2
5
1

と出力されます。

OrderedSet を使う

OrderedSetは、順序の概念が定義された 順序集合 です。

配列をもとに OrderedSet を生成する

toOrderedSetopenArray型の配列を渡すことで、重複要素を削除した集合、OrderedSet型の値を返します。

OrderedSetを宣言する
import sets

var mySet: OrderedSet[int] = toOrderedSet([2, 7, 3, 9, 4, 5, 4])
echo mySet

上のコードでは、{2, 7, 3, 9, 4, 5}が出力されます。

OrderedSet で適用できる機能

contains$containsOrInclexclcardlenmissingOrExclinclclear==hashitemsは、OrderedSetでも適用できます。
処理内容については、HashSetと同じです。

for文でindexと要素を走査する

OrderedSetでは、indexと要素を走査できるpairsというイテレータが定義されています。

pairで走査する
import sets

var mySet = toOrderedSet(["apple", "orange", "grape", "banana", "lemon"])

for index, elem in mySet.pairs:
  echo index, " ", elem

上のコードは、

結果
0 apple
1 orange
2 grape
3 banana
4 lemon

と出力されます。

SomeSet を使う

SomeSetは、HashSet型とOrderedSet型の共用型です。

終わりに

setsモジュールでは、集合の基本的な操作を始めとして、開発に役立つイテレータやプロシージャが定義されています。
ぜひ、活用してみてください。
SomeSet の使い道について、結局わからなかったのでコメントなどで指摘していただけると助かります。


  1. openArray型は、動的配列型seq、静的配列型arrayなど、様々な配列を受け入れる、引数専用の型です。 

  2. HashSet型は順序が保証されていないので環境によっては異なる順番で出力されることがあります。 

  3. 和集合とは、二つの集合のいずれかに属する要素のことで、例えば {1, 2, 3}{3, 4, 5} の和集合は {1, 2, 3, 4, 5}です。 

  4. 集合Aと集合Bの差集合とは、集合Aから集合Aと集合Bの共通要素を取り除いた集合のことで、例えば {1, 2, 3, 4, 5}{2, 4} の差集合は、{1, 3, 5}です。 

  5. 積集合とは、二つの集合の共通要素のことで、例えば {1, 2, 3, 9, 10, 11}{2, 5, 11} の積集合は {2, 11} です。 

  6. ある集合Aと集合Bの対称差とは、集合Aに属して集合Bに属さない要素と、集合Bに属して集合Aに属さない要素を全て集めてできる集合のことで、例えば {1, 2, 3, 4}{2, 4, 6, 7} の対称差は {1, 3, 6, 7}です。 

  7. ある二つの集合が互いに共通要素を持たない場合、素集合であると言います。 

  8. 集合Aが集合Bの厳密な部分集合であるとは、集合Bが集合Aの全ての要素を持っていて、かつ集合Aと集合Bは等しくないことを指します。 

  9. 集合Aが集合Bの部分集合であるとは、集合Bが集合Aの全ての要素を持っていることを指します。 

  10. 空集合とは、要素を一切持たない集合のことを指します。 

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
momeemt
こんにちは。高校3年生の樅山です。 Nimの記事を書いています。 標準ライブラリの解説をするのが好きです。
nim-in-japan
Nim言語の日本コミュニティです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?