8.1.9. Массивы как математические множества

8.1.9. Массивы как математические множества

В большинстве языков множества напрямую не реализованы (Pascal составляет исключение). Но массивы в Ruby обладают некоторыми свойствами, которые позволяют использовать их как множества. В данном разделе мы рассмотрим эти свойства и добавим свои собственные.

В последних версиях Ruby стандартная библиотека содержит класс Set. Если вам приходится часто иметь дело с множествами, подумайте об использовании объектов Set вместо массивов. Этот класс рассмотрен в главе 9.

Массив нельзя назвать идеальным средством для представления множества, поскольку он может содержать дубликаты. Если вы хотите трактовать массив как множество, то дубликаты можно удалить (с помощью метода uniq или uniq!).

Над множествами производятся две основные операции: объединение и пересечение. Для этого применяются операторы | (или) и & (и) соответственно. Поскольку множество по определению не содержит дубликатов, то повторяющиеся элементы удаляются (вопреки ожиданиям тех, кому доводилось работать с объединением и пересечением массивов в других языках).

а = [1, 2, 3, 4, 5]

b = [3, 4, 5, 6, 7]

с = a | b # [1, 2, 3, 4, 5, 6, 7]

d = а & b # [3,4,5]

# Дубликаты удаляются...

e = [1, 2, 2, 3, 4]

f = [2, 2, 3, 4, 5]

g = e & f # [2; 3, 4]

Для объединения множеств можно использовать и оператор конкатенации (+), но он не удаляет дубликаты.

Метод - соответствует операции «разность множеств»; результатом является множество, куда входят те элементы первого множества, которые не являются элементами второго (см. раздел 8.1.12).

а = [1, 2, 3, 4, 5]

b = [4, 5, 6, 7]

с = а - b # [1, 2, 3]

# Отметим, что наличие элементов 6 and 7 не отражается на результате.

Для «аккумулирования» множеств можно применять оператор |=; как и следовало ожидать, а |= b — то же самое, что а = а | b. Аналогичным образом оператор &= последовательно «сужает» множество.

Для массивов не определена операция ИСКЛЮЧАЮЩЕЕ ИЛИ, но мы можем без труда реализовать ее. В терминах теории множеств она соответствует выборке тех элементов, которые входят в объединение двух множеств, но не входят в их пересечение.

class Array

 def ^(other)

  (self | other) - (self & other)

 end

end

x = [1, 2, 3, 4, 5]

y = [3, 4, 5, 6, 7]

z = x ^ y # [1, 2, 6, 7]

Чтобы проверить, входит ли некий элемент в множество, пользуйтесь методом include? или member? (синоним, подмешанный из модуля Comparable):

x = [1, 2, 3]

if x.include? 2

 puts "yes" # Печатается "yes"

else

 puts "no"

end

Конечно, это некоторое отступление от канонов математики, где для обозначения принадлежности множеству применяется символ, похожий на греческую букву эпсилон. Отступление в том смысле, что множество находится слева, а не справа от оператора, то есть мы спрашиваем не «принадлежит ли данный элемент множеству», а «содержит ли множество данный элемент».

Многим это безразлично. Но привыкшие к языку Pascal или Python (или впитавшие математический формализм с молоком матери) хотели бы, чтобы было по-другому. Такую возможность мы реализуем в следующем фрагменте:

class Object

 def in(other)

  other.include? self

 end

end

x = [1, 2, 3]

if 2.in x

 puts "yes" # Печатается "yes"

else

 puts "no"

end

Лично я отправил запрос на изменение Ruby (RCR 241) с предложением ввести в язык оператор in. Он должен походить на одноименный оператор в языках Pascal, Python и даже SQL.

У этой идеи есть свои достоинства (к тому же in — уже зарезервированное слово), но единодушного одобрения она не получила. Может быть, оператор in появится в Ruby, а может, и нет.

Теперь обратимся к подмножествам и надмножествам. Как определить, является ли данное множество подмножеством или надмножеством другого? Встроенных методов для этого нет, но мы можем поступить следующим образом:

class Array

 def subset?(other)

  self.each do |x|

   if !(other.include? x)

    return false

   end

  end

  true

 end

 def superset?(other)

  other.subset?(self)

 end

end

a = [1, 2, 3, 4]

b = [2, 3]

с = [2, 3, 4, 5]

flag1 = c.subset? a   # false

flag2 = b.subset? a   # true

flag3 = c.superset? b # true

Обратите внимание: мы выбрали «естественный» порядок, то есть задаем вопрос x.subset?у — «является ли x подмножеством у?», а не наоборот.

Для распознавания пустого множества достаточно проверить, пуст ли массив. Это делает метод empty?.

Операция дополнения опирается на идею универсального множества. Однако «универсальное множество» в каждой конкретной ситуации определяется по-разному, поэтому лучшим решением будет самое простое: сначала определим, что такое универсальное множество, а потом вычислим разность.

universe = [1, 2, 3, 4, 5, 6]

а = [2, 3]

b = universe - а # Дополнение а = [1, 4, 5, 6]

Если считаете необходимым, можете определить и унарный оператор (например, - или ~ для выполнения этой операции.

Элементы множества можно перебирать, обходя массив. Единственная разница заключается в том, что элементы будут появляться в определенном порядке, а это может оказаться нежелательным. О том, как перебирать массив в случайном порядке, будет рассказано в разделе 8.1.18.

Наконец, иногда возникает необходимость вычислить степень множества. Это не что иное, как множество всех подмножеств данного множества (включая его само и пустое множество). Читатели, знакомые с дискретной математикой, в особенности с комбинаторикой, понимают, что число таких подмножеств равно 2n. Сгенерировать степень множества можно следующим образом:

class Array

 def powerset

  num = 2**size

  ps = Array.new(num, [])

  self.each_index do |i|

   a = 2**i

   b = 2**(i+1) — 1

   j = 0

   while j < num-1

    for j in j+a..j+b

     ps[j] += [self[i]]

    end

    j += 1

   end

  end

  ps

 end

end

x = [1, 2, 3]

y = x.powerset

# y равно:

#  [[], [1], [2], [1,2] , [3], [1,3], [2,3], [1,2,3]]

Данный текст является ознакомительным фрагментом.



Поделитесь на страничке

Похожие главы из других книг:

Математические формулы

Из книги автора

Математические формулы Кирпичи просто создавать, использовать, они понятны и просты, но на протяжении столетий возникло и сформировалось более тонкое понимание систем упорядочения. Эти открытия и нововведения развивали наше понимание сеток. Обращаясь к математике,


Математические функции

Из книги автора

Математические функции Имеющиеся в VBScript функции, предназначенные для математических вычислений, описаны в табл. П2.14.Таблица П2.14. Математические функции Функция Описание Abs(x) Возвращает абсолютное значение числа х Atn(x) Возвращает арктангенс числа х Cos(x) Возвращает


Математические функции

Из книги автора

Математические функции Функции округления absВозвращает модуль числа.Синтаксис:mixed abs(mixed $number)Тип параметра $number может быть float или int, а ти п возвращаемого значения всегда совпадает с типом этого параметра.$x = abs(-4); // $x=4$x = abs(-7.45); // $x=7.45roundОкругление дробного числа до


2.1. Предыстория. Математические основы

Из книги автора

2.1. Предыстория. Математические основы Представление различных понятий окружающего нас мира при помощи графической символики уходит своими истоками в глубокую древность. В качестве примеров можно привести условные обозначения знаков Зодиака, магические символы


4.1. Математические формулы

Из книги автора

4.1. Математические формулы В текстовом редакторе Word существует специальный инструмент для работы с формулами – редактор формул. С его помощью можно создавать сложные объекты, выбирая символы с панели инструментов и задавая переменные и числа. При этом размер шрифтов,


Стандартные математические функции

Из книги автора

Стандартные математические функции ABS (X) – абсолютная величина X.ARCTAN (X) – вычисление угла в радианах, тангенс которого равен X.COS (X) – вычисление косинуса угла в радианах.EXP (X) – Вычисление ex.LN (X) – вычисление натурального логарифма от X.PI – вычисление числа Пи.RANDOM –


Стандартные математические функции

Из книги автора

Стандартные математические функции Для того, чтобы использовать эти функции в начале программы должно стоять:#include <math. h>abs (x) – возвращает абсолютное значение целого аргумента x.acos (x) – арккосинус x.asin (x) – арксинус x.atan (x) – арктангенс x.cos (x) – косинус x.exp (x) – ex.fabs


Математические функции

Из книги автора

Математические функции Создайте чистую таблицу. Эту таблицу мы будем использовать для примеров использования функций.Наиболее часто используемая функция в математических расчетах – это КОРЕНЬ.1. Выделите ячейку R2C2. В эту ячейку мы будем вставлять функцию.2. Нажмите


Математические функции

Из книги автора

Математические функции Функция Краткое описание abs нахождение абсолютного значения выражения типа int acos вычисление арккосинуса asin вычисление арксинуса atan вычисление арктангенса х atan2 вычисление арктангенса от у/х cabs нахождение абсолютного значения


Математические функции

Из книги автора

Математические функции Интерфейс математических подпрограмм заимствован преимущественно из модулей System и Math системы Delphi. function Sign(x: integer): integer; Возвращает знак числа x function Sign(x: longword): integer; Возвращает знак числа x function Sign(x: int64): integer; Возвращает знак числа


Математические формулы для женщин

Из книги автора

Математические формулы для женщин Авторы: Скамейкин, Алексей, Яблоков, Сергей Две тысячи лет мужчины провели впустую. Вместо того чтобы написать формулу красоты и здоровья или хотя бы соорудить внятное определение красоты, они ходили вокруг да около, не в силах