Сравнение списков

Question

Я использую этот вопрос в интервью, и мне интересно, каково лучшее решение.

Напишите подпрограмму Perl, которая принимает n списков, а затем возвращает 2 ^ n -1 списков, сообщающих вам, какие элементы находятся в каких списках; то есть, какие элементы находятся только в первом списке, втором списке, как в первом, так и во втором списке, и во всех других комбинациях списков. Предположим, что n достаточно мало (менее 20).

Например:

list_compare([1, 3], [2, 3]);
  => ([1], [2], [3]);

Здесь первый список результатов дает все элементы, которые есть только в списке 1, второй список результатов дает все элементы, которые есть только в списке 2, а третий список результатов дает все элементы, которые есть в обоих списках.

list_compare([1, 3, 5, 7], [2, 3, 6, 7], [4, 5, 6, 7])
  => ([1], [2], [3], [4], [5], [6], [7])

Здесь первый список дает все элементы, которые есть только в списке 1, второй список дает все элементы, которые есть только в списке 2, а третий список дает все элементы, которые находятся в обоих списках 1 и 2, как в первый пример. Четвертый список дает все элементы, которые есть только в списке 3, пятый список дает все элементы, которые есть только в списках 1 и 3, шестой список дает все элементы, которые есть только в списках 2 и 3, и седьмой список дает все элементы которые есть во всех 3 списках.

Обычно я задаю эту проблему как продолжение этой проблемы для n = 2.

Какое решение?

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

Answer 1

Ваше решение можно еще немного упростить.

В первом цикле вы можете использовать простое сложение, так как вы всегда выполняете ИЛИ только с единичными битами, и вы можете сузить область действия $bit, перебирая индексы. Во втором цикле вы можете вычесть 1 из индекса вместо того, чтобы создавать ненужный 0-й элемент списка вывода, который должен быть shift удален, и где вы без необходимости итерируете m * n раз (где m - количество списков вывода и n - количество уникальных элементов), итерирование по уникальным элементам уменьшило бы итерации до просто n (что является значительным выигрышем в типичных случаях использования, когда m намного больше, чем n), и упростят код.

sub list_compare {
    my ( @list ) = @_;
    my %dest;

    for my $i ( 0 .. $#list ) {
        my $bit = 2**$i;
        $dest{$_} += $bit for @{ $list[ $i ] };
    }

    my @output_list;

    for my $val ( keys %dest ) {
        push @{ $output_list[ $dest{ $val } - 1 ] }, $val;
    }

    return \@output_list;
}

Также обратите внимание, что если подумать над этим, процесс сбора результатов можно записать очень кратко с помощью модуля List :: Part :

use List::Part;

sub list_compare {
    my ( @list ) = @_;
    my %dest;

    for my $i ( 0 .. $#list ) {
        my $bit = 2**$i;
        $dest{$_} += $bit for @{ $list[ $i ] };
    }

    return [ part { $dest{ $_ } - 1 } keys %dest ];
}

Но учтите, что list_compare это ужасное имя. Что-то вроде part_elems_by_membership было бы намного лучше. Кроме того, неточности в вашем вопросе, на которые указал Бен Тилли, необходимо исправить.

Answer 2

Прежде всего, я хотел бы отметить, что ничейный ответ просто не работает. Попробуйте запустить его и посмотрите на вывод в Data :: Dumper, чтобы убедиться в этом.

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

sub list_compare {
  my @lists = @_;

  my @answers;
  for my $list (@lists) {
    my %in_list = map {$_=>1} @$list;
    # We have this list.
    my @more_answers = [keys %in_list];
    for my $answer (@answers) {
      push @more_answers, [grep $in_list{$_}, @$answer];
    }
    push @answers, @more_answers;
  }

  return @answers;
}

Если вы хотите скорректировать эти предположения, вам нужно будет скорректировать код. Например, не сжатие сложных структур данных и не дублирование дубликатов можно сделать с помощью:

sub list_compare {
  my @lists = @_;

  my @answers;
  for my $list (@lists) {
    my %in_list = map {$_=>1} @$list;
    # We have this list.
    my @more_answers = [@$list];
    for my $answer (@answers) {
      push @more_answers, [grep $in_list{$_}, @$answer];
    }
    push @answers, @more_answers;
  }

  return @answers;
}

Это, однако, использует строковую структуру структуры данных, чтобы проверить, существуют ли вещи, которые существуют в одном, в другом. Чтобы ослабить это состояние, потребуется немного больше работы.

Answer 3

Вот мое решение:

Создайте хэш, ключи которого являются объединением всех элементов в списках ввода, а значения являются битовыми строками, где бит i устанавливается, если элемент присутствует в списке i . Битовые строки создаются с использованием побитового или. Затем создайте выходные списки, перебирая ключи хеша, добавляя ключи в связанный выходной список.

sub list_compare {
    my (@lists) = @_;
    my %compare;
    my $bit = 1;
    foreach my $list (@lists) {
        $compare{$_} |= $bit foreach @$list;
        $bit *= 2; # shift over one bit
    }


    my @output_lists;
    foreach my $item (keys %compare) {
        push @{ $output_lists[ $compare{$item} - 1 ] }, $item;
    }

    return \@output_lists;

}

Обновлено, чтобы включить генерацию инвертированного списка вывода, предложенную Аристотелем