Программирование на языке Ruby, Фултон Хэл

Программирование на языке Ruby

на обложку

Фултон Хэл

Шрифт:

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

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

x = [1, 2, 3]

y = x.powerset

# y равно:

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

8.1.10. Рандомизация массива

Иногда нужно переставить элементы массива в случайном порядке. Первое, что приходит на ум, — тасование карточной колоды, но есть и другие применения — например, случайная сортировка списка вопросов.

Для решения этой задачи пригодится метод

rand

из модуля Kernel. Ниже показан один из возможных способов:

class Array

def randomize

self.sort_by { rand } # Сортировать по ключу, являющемуся

end # случайным числом.

def randomize!

self.replace(self.randomize)

end

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

y = x.randomize # [3, 2, 4, 1, 5]

x.randomize! # x равно [3, 5, 4, 2]

Из-за

самой природы сортировки, вероятно, вносится некоторое статистическое смещение. Но обычно это не играет роли.

Выбрать случайный элемент массива (не запрещая дубликатов) можно так:

class Array

def pick_random

self[rand(self.length)]

end

Наконец, не стоит забывать, что метод

rand

позволяет сгенерировать предсказуемую последовательность (например, для тестирования), если затравить алгоритм известным значением с помощью метода

srand

(см. раздел 5.28).

8.1.11. Многомерные массивы

Если для численного анализа вам нужны многомерные массивы, то в архиве приложений Ruby есть прекрасная библиотека

NArray

, которую написал Масахиро Танака (Masahiro Tanaka). Если необходим аппарат для работы с матрицами, обратитесь к стандартной библиотеке matrix.rb, которая была упомянута в разделе 5.10.

В следующем примере показан способ работы с многомерными массивами за счет перегрузки методов

[]

[]=

для отображения элементов на вложенный массив. Представленный класс

Array3

обеспечивает рудиментарные операции с трехмерными массивами, но он далеко не полон:

class Array3

def initialize

@store = [[[]]]

end

def [](a,b,c)

if @store[a]==nil ||

@store[a][b]==nil ||

@store[a][b][c]==nil

return nil

else

return @store[a][b][c]

end

def []=(a,b,c,x)

@store[a] = [[]] if @store[a]==nil

@store[a][b] = [] if @store[a][b]==nil

@store[a][b][с] = x

end

x = Array3.new

x[0,0,0] = 5

x[0,0,1] = 6

x[1,2,31 = 99

puts x[1,2,3]

Единственное, чего мы реально добились, — так это удобного использования запятой в обозначении

[x,y,z]

вместо употребляемой в языке С нотации

[x][у][z]

. Если C-подобная нотация вас устраивает, можете просто воспользоваться вложенными массивами Ruby. Еще одно мелкое достоинство — предотвращение ситуации, когда объектом, от имени которого вызывается оператор

[]

, оказывается

nil