Sets

Olá, sejam bem-vindos a mais uma aula do nosso curso! Hoje vamos falar sobre conjuntos, ou sets, em inglês. Começaremos entendendo a ADT (Abstract Data Type) de um conjunto, veremos como usar Sets em Ruby e por fim implementaremos nosso próprio Set utilizando arrays - que é o a estrutura que temos em nossa caixa de ferramentas por hora.

ADT

  • build(X) - O(n)
  • add - O(1)
  • remove O(1)
  • has O(1)
  • merge O(n)
  • subset

Trabalhando com Sets em Ruby

Uma propriedade da estrutura Set é manter apenas uma ocorrência do item. Diferente do array, um Set não acomoda um mesmo item duas vezes.

Criando um set

irb(main):012> s = Set.new
=> #<Set: {}>
irb(main):013> s.add(10)
=> #<Set: {10}>
irb(main):014> s.add?(10)
=> nil
irb(main):015> s.add?(nil)
=> #<Set: {10, nil}>
irb(main):016> s.add?(nil)
=> nil
irb(main):017> s.add(nil)
=> #<Set: {10, nil}>
irb(main):018> s2 = Set.new([1, 2, 3])
=> #<Set: {1, 2, 3}>
irb(main):019> s.merge(s2)
=> #<Set: {10, nil, 1, 2, 3}>
irb(main):020> s3 = Set.new([1, 2, 3]) { |x| x^2 }
=> #<Set: {3, 0, 1}>
irb(main):021> s3 = Set.new([1, 2, 3]) { |x| x^2 }
=> #<Set: {3, 0, 1}>
irb(main):022> s3 = Set.new([1, 2, 3]) { |x| x**x }
=> #<Set: {1, 4, 27}>
irb(main):023> s3 = Set.new([1, 2, 3]) { |x| x**x }
=> #<Set: {1, 4, 27}>
irb(main):024> 3^2
=> 1
irb(main):025> 3**2
=> 9
irb(main):026> s3 = Set.new([1, 2, 3]) { |x| x**2 }
=> #<Set: {1, 4, 9}>

Set a partir de um array

irb(main):027> [1, 2, 3, 3, 3, 3].to_set
=> #<Set: {1, 2, 3}>

Implementando nosso próprio Set usando arrays

Vamos criar um set utilizando arrays

Conclusão

Encerramos assim nossa aula sobre Sets. Espero que tenham gostado e até a próxima!

Referências