0

私はこの質問をインタビューで使用しますが、最善の解決策は何でしょうか。

n個のリストを取得して2^ n -1個のリストを返し、どの項目がどのリストにあるかを示すPerlサブを記述します。つまり、最初のリスト、2番目のリスト、1番目と2番目のリストの両方、およびその他すべてのリストの組み合わせにのみ含まれるアイテムです。nが適度に小さい（20未満）と仮定します。

例えば：

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

ここで、最初の結果リストはリスト1のみにあるすべてのアイテムを示し、2番目の結果リストはリスト2のみにあるすべてのアイテムを示し、3番目の結果リストは両方のリストにあるすべてのアイテムを示します。

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

ここで、最初のリストはリスト1のみにあるすべてのアイテムを示し、2番目のリストはリスト2のみにあるすべてのアイテムを示し、3番目のリストは最初の例のようにリスト1と2の両方にあるすべてのアイテムを示します。4番目のリストはリスト3にのみ存在するすべてのアイテムを示し、5番目のリストはリスト1と3にのみ存在するすべてのアイテムを示し、6番目のリストはリスト2と3にのみ存在するすべてのアイテムを示し、7番目のリストはすべてのアイテムを示します。 3つのリストすべてに含まれています。

私は通常、この問題をn =2の場合のこの問題のサブセットのフォローアップとして提供します。

解決策は何ですか？

フォローアップ：リストの項目は文字列です。重複がある可能性がありますが、それらは単なる文字列であるため、重複は出力で潰す必要があります。出力リスト内のアイテムの順序は重要ではなく、リスト自体の順序も重要です。

4

3 に答える 3

2

あなたの与えられた解決策は、まだかなり単純化できます。

最初のループでは、単一のビットでのみ OR 演算を行うため、単純な加算を使用できます。また、$bitインデックスを反復処理することで範囲を狭めることができます。2 番目のループでは、削除する必要がある不要な 0 番目の出力リスト要素を生成する代わりに、インデックスから 1 を引くことができ、不必要にshiftm*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がはるかに良いでしょう。また、Ben Tilly が指摘した質問の不正確さを修正する必要があります。

于 2008-09-16T09:33:47.660 に答える
1

まず第一に、nohatの答えは単に機能しないことに注意したいと思います。それを実行してみて、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;
}

ただし、これはデータ構造の文字列化を使用して、あるものに存在するものが別のものに存在するかどうかをチェックしています。その状態を緩和するには、いくらか多くの作業が必要になります。

于 2008-09-16T07:18:43.477 に答える
0

これが私の解決策です：

キーが入力リスト内のすべての要素の和集合であり、値がビット文字列であるハッシュを作成します。要素がリスト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;

}

アリストテレスによって提案された反転出力リストの生成を含むように更新されました

于 2008-09-16T01:05:47.430 に答える