bugfix> javascript > 投稿

たとえば、2つの配列があります(最初の配列には名と2番目の配列の姓が含まれています)。この2つの配列からこのような順序でn個の一意の非繰り返しの組み合わせを生成したい>>> first_name + '' + last_name。

すべての可能な組み合わせを事前に生成することは望ましくありません。これは、メモリを大量に消費するためです。

したがって、アルゴリズムが行うべきだと思うことは、組み合わせが生成されなくなるまで繰り返し、繰り返し中に両方の配列にいくつかのランダムインデックスを与える必要があり、それらのインデックスが既に一緒に使用されている場合、一意のインデックスが生成されなくなるまで別の乱数を選択しようとします。 ただし、多くの出力が既に与えられているため、このアプローチは実行時に深い再帰をトリガーする可能性があります。これは、新しいランダムインデックスが既存のインデックスと一致する可能性が各ステップで高くなるためです。

あなたの提案者は何ですか、非常に最適化された方法で、存在しない/仮想2配列要素の組み合わせからランダムでユニークなn個のアイテムを選択するにはどうすればよいですか

回答 1 件
  • F個の一意の姓とL個の一意の姓がある場合、組み合わせの総数は N = F * L です

    したがって、必要な数の範囲 0..N-1 で非反復ランダム整数値を生成できます  (たとえば、Fisher-Yatesサンプリングを使用)、並べ替え、対応する名前の組み合わせを取得します。

    for i = 0..M-1
        Generate K[i] = Random(N)
    Sort K[]
    for i = 0..M-1
       FirstNameIndex = K[i] / L    //integer division
       LastNameIndex = K[i] % L     //integer modulo
       Combination[i] = First[FirstNameIndex] + Last[LastNameIndex]
    
    

あなたの答え