각 배열에 포함 된 요소로 배열 배열 정렬

Question

그래프에서 연결된 모든 구성 요소를 트래버스해야합니다. 그래프의 경로가 이런 배열에 저장된다 : 여기

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

내가 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] 

인해 요소의 많은 양의, 내가 재귀를 사용하지 않으 것입니다. 다른 모든 배열에 포함 된 한 배열의 요소로이 배열 목록을 정렬하는 방법이 있습니까? 그래서 반복 할 때 처리 할 수 ​​있습니까?

는

편집 : 나는이로 구성된 각 경로에 가중치를 할당함으로써 해결 될 수 있다고 생각 다음 :이 노드가 다른 경로에 포함되는 횟수를 곱한 각 경로에 포함 된 노드의 합, 다음 경로를 정렬 길이 오름차순 및 체중 내림차순 -하지만 이것은 단지 내 추측입니다 ...

Answer 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);

이 좋아 우리는 첫 번째 개체 (lut)를 같은 룩업 테이블에서이 특정한 경우에 그것은 그래서 우리는 지금 6가 그 경로를 알고

{ '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': [ [ 3, 1 ], [ 0, 2 ], [ 2, 4 ] ],은 paths[3]에 있음을 의미합니다. paths[0]에는 단일 종속이 있고 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) ,[]) 라인이 조금 재미 있습니다. 그것이하는 일은 각 경로가 그것의 배열을 "if"배열로 밀어 넣는 것입니다. 그래서 우리는 가장 의존적 인 것부터 시작합니다 (6). 우리는 3, 0, 2를 밀었습니다. 그래서 5의 차례가 올 때 우리는 같은 인덱스를 다시 누르지 않을 것입니다.