如何从多个数组中挑选数组，使所有元素都以线性方式上升

Question

我有一张包含这些阵列的地图。我想要的是从 0-10 中选择最少的项目。例如。

 {
      '11100171' => [ 0, 1, 2, 3 ],
      '11100060' => [ 1, 2, 3 ],
      '12100062' => [ 4 ],
      '12100012' => [ 5, 6, 7 ],
      '12100011' => [ 6, 7 ],
      '12100020' => [ 7 ],
      '12100121' => [ 7 ],
      '11100130' => [ 8, 9 ],
      '11100140' => [ 8, 9 ],
      '11100470' => [ 8, 9 ],
      '11400080' => [ 8, 9, 10 ]
    }

我会选择

'11100171' => [0,1,2,3],
'12100062'=> [4],
'12100012' => [5,6,7],
'11400080' => [8,9,10]

从这里开始。

Answer 1

这是一个图形寻路问题。如果我们假设所有数组都由连续的数字组成，我们可以将一个这样的数组解释为图中的一条边，该边将第一个数字标识的节点与最后一个数字加 1 标识的节点连接起来。

然后目标就是找到从起点到终点+1的最短路径。

为此，我们可以在该图中使用 breadth-first 搜索。

下面是 JavaScript 这个想法的实现：

function createAdjacencyList(data) {
    let adj = {};
    for (let key in data) {
        let arr = data[key];
        let start = arr[0];
        if (!adj[start]) adj[start] = [];
        adj[start].push(arr);
    }
    return adj;
}

function shortestPath(adj, start, end) { // BFS algo
    let frontier = [start];
    let comeFrom = {};
    while (frontier.length) {
        let nextFrontier = [];
        for (let node of frontier) {
            if (node === end + 1) { // Unwind path
                let path = [];
                do {
                    arr = comeFrom[node];
                    path.push(arr);
                    node = arr[0];
                } while (node != start);
                return path.reverse();
            }
            if (adj[node]) {
                for (let arr of adj[node]) {
                    let neighbor = arr.at(-1) + 1;
                    if (!comeFrom[neighbor]) {
                        comeFrom[neighbor] = arr;
                        nextFrontier.push(neighbor);
                    }
                }
            }
        }
        frontier = nextFrontier;
    }
}

// Example run
let data = {
  '11100171': [0, 1, 2, 3],
  '11100060': [1, 2, 3],
  '12100062': [4],
  'aaaaaaaa': [4, 5],
  '12100012': [5, 6, 7],
  '12100011': [6, 7],
  '12100020': [7],
  '12100121': [7],
  '11100130': [8, 9],
  '11100140': [8, 9],
  '11100470': [8, 9],
  '11400080': [8, 9, 10],
  'xxxxxxxx': [9, 10]
};

let adj = createAdjacencyList(data);
let path = shortestPath(adj, 0, 10);
for (let arr of path) {
    console.log(...arr);
}

如何从多个数组中挑选数组，使所有元素都以线性方式上升

How to pick arrays from many arrays so that all elements are rising in a linear way

algorithm

data-structures