セット

セット（Set; 集合）は、データ構造の一つで、重複を許さず、順序の概念がない要素の集まりを表します。集合は、数学の集合論に基づいて設計されたものであり、集合を操作するための様々な演算が定義されています。 集合には以下のような基本的な操作があります。

操作のインターフェース:

• Addition（要素の追加）: 集合に新しい要素を追加します。
• Removal（要素の削除）: 集合から指定した要素を削除します。
• Contains（要素が集合に属すか判定）: 集合に指定した要素が含まれているかを判定します。x ∈ A
• Union（和集合）: 2つの集合の要素を合わせて新しい集合を作ります。A ∪ B
• Intersection（積集合）: 2つの集合に共通する要素を集めて新しい集合を作ります。A ∩ B
• Difference（差集合）: 2つの集合のうち、1つ目の集合には含まれるが2つ目の集合には含まれない要素を集めて新しい集合を作ります。A \ B
• Subset（部分集合の判定）: 1つの集合が別の集合の部分集合であるかどうかを判定します。A ⊆ B

実装例

Ruby

Rubyには、既に Set クラスがありますが、ここでは Array を継承して実装しました。

RubyでSetを実装

# frozen_string_literal: true

class MySet < Array
  def initialize(*args, &block)
    @head = nil
    case [args, block]
    in [], nil then return
    in [Array => ary], nil then ary.each { add _1 }
    in [Array => ary], block then ary.each { add block[_1] }
    in [Integer => size], nil if size >= 0 then size.times { add _1 }
    in [Integer => size], block if size >= 0 then size.times { add block[_1] }
    else raise ArgumentError, "#{self.class}#initialize: #{args.inspect} #{block && 'block_given!'}"
    end
  end

  # 要素の追加
  def add(element)
    self << element unless contains?(element)
  end
  
  # 要素の削除
  alias remove delete

  # 要素の検索
  alias contains? include?

  # 集合の和
  def union(other) = self.class.new(self + other)

  # 集合の積
  def intersection(other) = self.class.new(self & other)

  # 集合の差
  def difference(other) = self.class.new(self - other)

  # 部分集合の判定
  def subset?(other) = other.size === 0 || all? { |element| other.contains?(element) }
end

require 'minitest/autorun'

describe MySet do
  let(:set0) { MySet.new }
  let(:set12) { MySet.new [1, 2] }
  let(:set23) { MySet.new [2, 3] }

  describe '#initialize' do
    it 'initializes with no arguments' do
      expect(MySet.new).must_equal set0
    end

    it 'initializes with an array argument' do
#      expect(MySet.new([1, 2, 3])).must_equal MySet.new(1, 2, 3)
    end

    it 'initializes with an array argument and block' do
      expect(MySet.new([4, 14, 6])).must_equal MySet.new([2, 7, 3]) { |x| 2 * x }
    end

    it 'initializes with a size argument' do
      expect(MySet.new([0, 1, 2])).must_equal MySet.new(3)
    end

    it 'initializes with a size argument and block' do
      expect(MySet.new([1, 3, 5])).must_equal MySet.new(3) { |x| 2 * x + 1}
    end

    it 'raises ArgumentError with invalid arguments' do
      expect { MySet.new('invalid') }.must_raise ArgumentError
      expect { MySet.new(-1) }.must_raise ArgumentError
      expect { MySet.new(1, 2, 3) { |x| x } }.must_raise ArgumentError
    end
  end

  describe '#add' do
    it 'adds an element to the set' do
      set0.add(1)
      expect(set0).must_equal MySet.new([1])
    end

    it 'does not add an element already in the set' do
      set0.add(1)
      set0.add(1)
      expect(set0).must_equal MySet.new([1])
    end
  end

  describe '#remove' do
    it 'removes an element from the set' do
      set0.add(1)
      set0.remove(1)
      expect(set0).must_equal MySet.new
    end
  end

  describe '#contains?' do
    it 'returns true if the set contains the element' do
      set0.add(1)
      expect(set0.contains?(1)).must_equal true
    end

    it 'returns false if the set does not contain the element' do
      expect(set0.contains?(1)).must_equal false
    end
  end

  describe '#union' do
    it 'returns the union of two sets' do
      expect(set12.union(set23)).must_equal MySet.new([1, 2, 3])
    end
  end

  describe '#intersection' do
    it 'returns the intersection of two sets' do
      expect(set12.intersection(set23)).must_equal MySet.new([2])
    end
  end

  describe '#difference' do
    it 'returns the difference of two sets' do
      expect(set12.difference(set23)).must_equal MySet.new([1])
    end
  end

  describe '#subset?' do
    it 'returns true if the set is a subset of another set' do
      set12 = MySet.new([1, 2])
      set123 = MySet.new([1, 2, 3])
      expect(set12.subset?(set123)).must_equal true
      expect(set123.subset?(set12)).must_equal false
    end

    it 'returns false if the set is not a subset of another set' do
      expect(set12.subset?(set23)).must_equal false
      expect(set23.subset?(set12)).must_equal false
    end

    it 'returns true if the set is a subset of empty set' do
      expect(set12.subset?(set0)).must_equal true
    end

    it 'returns true if the set is a subset of set self' do
      expect(set12.subset?(set12)).must_equal true
    end
  end
end