Perl. Библиотека программиста

Вычисление объединения, пересечения и разности уникальных списков

Проблема

Имеются два списка, каждый из которых содержит неповторяющиеся элементы. Требуется узнать, какие элементы присутствуют в обоих списках (пересечение), присутствуют в одном и отсутствуют в другом списке (разность) или хотя бы в одном из списков (объединение).

Решение

В приведенных ниже решениях списки инициализируются следующим образом:

@a = (1, 3, 5, 6, 7, 8);
@b = (2, 3, 5, 7, 9);
@unuon = @isect = @diff = ();
%unuon = %isect = ();
%count = ();

Простое решение для объединения и пересчения

foreach $e (@a) {$inion{$e} = 1;}
foreach $e (@b) {
  if ( $union {$e} ) { $isect{$e} = 1; }
  $union {$e} = 1;
}
@unuon = keys %union;
@isect = keys %isect;

Идиоматическое решение

foreach $e (@a, @b) {$inion{$e}++ && $isect{$e}++;}
@unuon = keys %union;
@isect = keys %isect;

Объединение, пересечение и симметричная разность

foreach $e (@а, @b) { $count{$e}++; }
foreach $e (keys %count) {
  push(@union, $e);
  if ($count{$e} == 2) {
    push @isect, $e;
  } else {
      push @diff, $e;
    }
}

Косвенное решение

@isect = @diff = @union = ();
foreach $e (@a, @b) { $count{$e}++; }
foreach $e (keys %count) {
  push(@union, $e);
  push @{ $count{$e) == 2 ? \@isect : \@diff }, $e;
}

Комментарий

В первом решении происходит непосредственное вычисление объединения и пересечения двух списков, ни один из которых не содержит дубликатов. Для записи элементов, принадлежащих к объединению и пересечению, используются два разных хэша. Сначала мы заносим каждый элемент первого массива в хэш объединения и ассоциируем с ним истинное значение. Затем при последовательной обработке элементов второго массива мы проверяем, присутствует ли элемент в объединении. Если присутствует, он также включается и в хэш пересечения. В любом случае элемент заносится в хэш объединения. После завершения перебора мы извлекаем ключи обоих хэшей. Ассоциированные с ними значения не нужны.

Второе решение («Идиоматическое») в сущности делает то же самое, однако для него потребуется хорошее знание операторов Perl (а также awk, С, C++ и Java) ++ и &&. Если ++ находится после переменной, то ее старое значение используется до приращения. Когда элемент встречается впервые, он еще отсутствует в объединении, поэтому первая часть && будет ложной, а вторая часть попросту игнорируется. Когда тот же элемент встретится во второй раз, он уже присутствует в объединении, поэтому мы заносим его и в пересечение.

В третьем решении использован всего один хэш для хранения информации о том, сколько раз встретился тот или иной элемент. Записав элементы обоих массивов в хэш, мы последовательно перебираем его ключи. Каждый ключ автоматически попадает в объединение. Ключи, с которыми ассоциировано значение 2, присутствуют в обоих массивах и потому заносятся в массив пересечения. Ключи с ассоциированным значением 1 встречаются лишь в одном из двух массивов и заносятся в массив разности. В отличие от исходного решения, порядок элементов в выходных массивах не совпадает с порядком элементов входных массивов.

В последнем решении, как и в предыдущем, используется всего один хэш с количеством экземпляров каждого элемента. Однако на этот раз реализация построена на массиве в блоке @{...}.

Мы вычисляем не простую, а симметричную разность. Эти термины происходят из теории множеств. Симметричная разность представляет собой набор всех элементов, являющихся членами либо @А, либо @В, но не обоих сразу. Простая разность — набор всех элементов @А, отсутствующих в @В.

Вычисление объединения, пересечения и разности уникальных списков

Проблема

Решение

Комментарий

См. также