Belirli düğümler verilen tüm olası yollar, başlangıç ​​düğümüne dön

Question

Şu anda tüm düğümleri ziyaret etme ve düğümü başlatmak için tüm olası kombinasyonları çıkaran küçük bir sorun üzerinde çalışıyorum.

I ["a", "b", "c"] bütün muhtemel yolları olan bir dizi üç düğümden

pairs = [ [ 'a', 'b' ], 
    [ 'a', 'c' ], 
    [ 'b', 'a' ], 
    [ 'b', 'c' ], 
    [ 'c', 'a' ], 
    [ 'c', 'b' ] ]; 

yolları oluşturmak için My fonksiyonu (__ çizgi kitaplığı için) olan

routesRecursive = function(pairs, currentNode, origin, result) { 
    __.each(pairs, function(pair) { 
    if (currentNode === __.first(pair)) { 
     var currentRoute = pair; 
     var nextNode = __.last(currentRoute); 
     if (nextNode === origin) { 
     result.push(pair); 
     } else { 
     result.push(currentRoute); 
     routesRecursive(__.without(pairs, currentRoute), nextNode, origin, result); 
     } 
    } 
    }); 
    return result; 
} 
routesRecursive(pairs, "a", "a", []) 

İstenen çıkış olacaktır:

[ 
    [["a", "b"], ["b", "a"]], 
    [["a", "b"], ["b", "c"], ["c", "a"]], 
    [["a", "b"], ["b", "c"], ["c", "b"], ["b", "a"]], 
    [["a", "c"], ["c", "a"]], 
    [["a", "c"], ["c", "b"], ["b", "a"]], 
    [["a", "c"], ["c", "b"], ["b", "c"], ["c", "a"]] 
] 

Fonksiyonum istenilen sonucu üretebiliyor gibi görünmüyor, herhangi bir öneri var mı?

Teşekkürler!

Answer 1

Bu deneyin:

function paths({ graph = [], from, to }, path = []) { 
 
    const linkedNodes = memoize(nodes.bind(null, graph)); 
 
    return explore(from, to); 
 

 
    function explore(currNode, to, paths = []) { 
 
     path.push(currNode); 
 
     for (let linkedNode of linkedNodes(currNode)) { 
 
      if (linkedNode === to) { 
 
       let result = path.slice(); // copy values 
 
       result.push(to); 
 
       paths.push(result); 
 
       continue; 
 
      } 
 
      // do not re-explore edges 
 
      if (!hasEdgeBeenFollowedInPath({ 
 
        edge: { 
 
         from: currNode, 
 
         to: linkedNode 
 
        }, 
 
        path 
 
       })) {      
 
       explore(linkedNode, to, paths); 
 
      } 
 
     } 
 
     path.pop(); // sub-graph fully explored    
 
     return paths; 
 
    } 
 
} 
 

 
/** 
 
* Get all nodes linked 
 
* to from `node`. 
 
*/ 
 
function nodes(graph, node) { 
 
    return graph.reduce((p, c) => { 
 
     (c[0] === node) && p.push(c[1]); 
 
     return p; 
 
    }, []); 
 
} 
 

 
/** 
 
* Has an edge been followed 
 
* in the given path? 
 
*/ 
 
function hasEdgeBeenFollowedInPath({ edge, path }) { 
 
    var indices = allIndices(path, edge.from); 
 
    return indices.some(i => path[i + 1] === edge.to); 
 
} 
 

 
/** 
 
* Utility to get all indices of 
 
* values matching `val` in `arr`. 
 
*/ 
 
function allIndices(arr, val) { 
 
    var indices = [], 
 
     i; 
 
    for (i = 0; i < arr.length; i++) { 
 
     if (arr[i] === val) { 
 
      indices.push(i); 
 
     } 
 
    } 
 
    return indices; 
 
} 
 

 
/** 
 
* Avoids recalculating linked 
 
* nodes. 
 
*/ 
 
function memoize(fn) { 
 
    const cache = new Map(); 
 
    return function() { 
 
     var key = JSON.stringify(arguments); 
 
     var cached = cache.get(key); 
 
     if (cached) { 
 
      return cached; 
 
     } 
 
     cached = fn.apply(this, arguments) 
 
     cache.set(key, cached); 
 
     return cached;; 
 
    }; 
 
} 
 
const graph = [ 
 
    ['a', 'b'], 
 
    ['a', 'c'], 
 
    ['b', 'a'], 
 
    ['b', 'c'], 
 
    ['c', 'a'], 
 
    ['c', 'b'] 
 
]; 
 
document.write(JSON.stringify(paths({ 
 
    graph, 
 
    from: 'a', 
 
    to: 'a' 
 
})));