配列の配列を各配列に含まれる要素で並べ替えます。

Question

グラフ内のすべての接続コンポーネントをトラバースする必要があります。 グラフのパスは、このような配列に格納されている：ここ

var paths = [ 
    [5,6], 
    [1,2], 
    [4,7,5,6], 
    [6] 
] 

iはpaths[2]=[4,7,5,6]が順番にpaths[3]=[6]から依存paths[0]=[5,6]から依存していることを見ます。

今、私は再帰的に他のものに含まれているものをチェックするためにすべてのパスをトラバースする必要があり、最初に他のものを解決するのに役立つものを処理します。 ：

例：

process [6] 
process [5,6] 
process [4,7,5,6] 
process [1,2] 

ための要素を大量に、私は再帰を使用しないでしょう。 他のすべての配列に含まれる1つの配列の要素によって、この配列のリストをソートする方法はありますか？

編集：私は、これは次のように構成される各パスに重みを割り当てることによって解決することができる 考える：このノードが他のパスに含まれている回数を乗じ、各パスに含まれるノードの 和を、次にパスを並べ替えます長さの昇順と重量の降順で - しかし、これは私の推測だけです...

Answer 1

私は正しく理解していれば、従属ソート後です。そして、私はこの仕事を達成するための可能な方法は次の通りだと考えています。これは私が思い付くかもしれない1つの方法ですが、より簡単な解決法もあるかもしれません。

お互いに依存する連続した項目のグループ（例えば[6],[5,6]、[4,7,5,6]など）を作成し、それらの依存関係に従って並べ替える必要があります。アイテムが関連付けられていない（つまり[1,2]はソートされたグループの前後に来る可能性があるので[6]、[5,6]および[4,7,5,6]）、別々のグループ間の並べ替えは不要です。

var paths = [ 
 
      [5,6], 
 
      [1,2], 
 
      [4,7,5,6], 
 
      [6] 
 
      ], 
 
     lut = paths.reduce((table,path,i) => (path.forEach(n => table[n] = table[n] ? table[n].concat([[i,path.length]]) 
 
                          .sort((a,b) => a[1]-b[1]) 
 
                        : [[i,path.length]]), 
 
              table),{}), 
 
    sorted = Object.keys(lut).sort((a,b) => lut[b].length - lut[a].length) 
 
          .reduce((si,k) => (lut[k].forEach(e => !si.includes(e[0]) && si.push(e[0])),si) ,[]) 
 
          .map(idx => paths[idx]); 
 
console.log(sorted);

[OK]を、私たちは、最初のオブジェクト（lut）のようなルックアップテーブルから、この特定のケースでは、それは

{ '1': [ [ 1, 2 ] ], 
    '2': [ [ 1, 2 ] ], 
    '4': [ [ 2, 4 ] ], 
    '5': [ [ 0, 2 ], [ 2, 4 ] ], 
    '6': [ [ 3, 1 ], [ 0, 2 ], [ 2, 4 ] ], 
    '7': [ [ 2, 4 ] ] 
} 

みたいに形成だから我々は今、そのパス6を持って知っています最も依存している。 '6': [ [ 3, 1 ], [ 0, 2 ], [ 2, 4 ] ],は、paths[3]にあることを意味します。 paths[0]には1つの依存関係があり、paths[2]には3人の扶養家族がいます。だから私たちは従属人数（.sort((a,b) => a[1]-b[1])）に従ってソートしました。 テーブルを作成したら、必要なインデックスマッピングを与えるだけです。 .reduce((si,k) => (lut[k].forEach(e => !si.includes(e[0]) && si.push(e[0])),si) ,[])行はちょっと面白いです。それがするのは、各パスが配列に配列を挿入していない場合に、その配列に配列を挿入することです。したがって、最も依存度の高いもの（6）から始めて、3、0、2を押します。したがって、5のターンが来ると、再び同じ指標を押し込むことはありません。