爪哇 - 查找所有可能的路径基于阵列的密钥对

Question

我有几个密钥对的数组，我想找到一个元素并返回所有可能的路径给它如：

array { 

a-b 
a-c 
a-d 
b-a 
b-c 
b-s 
d-c 
c-a 
c-d 
c-a 
d-a 
.... 

} 

我做一些foreach循环，但我坚持给定的数据集。有没有更好的方法来做到这一点？

这是我做过什么：

1）独立的所有键

new array1 = {a,b,c,d,e,f,g......} 

2）foreach循环，找到它的直接路径，例如：

'a' => b , c , d , e .... 
'b' => a , c, d, e 

3）我卡在这里

ab，现在来自b-有很多不同的路径，它可以采取，我不知道如何d为所有不同的可能路径嵌套。

任何帮助，将不胜感激

什么，我期待：

a-b-a 
a-b-c-a 
a-b-d-a 
a-b-e-a 
a-b-c-d-a 
a-b-c-e-a 
a-c-b-e-a 
a-e-c-b-a 
....... 

Answer 1

你可以做一个循环继续，直到所有路径，并开始用相同的节点结束。即您从包含仅仅起始节点的单个路径列表开始。为每个邻居复制路径，追加邻居并将其添加到列表中。重复，直到列表中的所有路径开始并以相同的节点结束。

您还需要进行一些检查以避免无限循环。

Answer 2

最简单的解决方案是枚举给定节点对的所有可能路径。 我敢肯定，我差点忘了一些案件，但这个应该是一个循环，遍历对一些+清理操作中实现的：

List<Path> paths = new ArrayList<>(); 
for (Pair p : pairs) { 
    // add the path created by this pair 
    paths.add(new Path(p)); 

    // find paths that contain this pair's starting edge and fork them 
    List<Path> forkedPaths = new ArrayList<>(); 
    for (Path path : paths) { 
     if (path.contains(p.getStart()) { 
      // fork creates a new path: (a-b-c).fork(b-d) = (a-b-d) 
      forkedPaths.add(path.fork(p)); 
     } 
    } 
    paths.addAll(forkedPaths); 
} 
removeDuplicates(paths); 

在这之后，你应该有一个排序的路径列表：

a-b-a 
c-d 
c-d-a 

哪个更容易检查您的预期状况。

这不是计算上最佳的，但应该提供一个很好的起点。

Answer 3

你可以看看这门课并测试它。 这不是最干净的方式，但我想这是一个开始。

public class TestRecursiveResearch { 

    public String[] myList = {"a-b", "a-d", "b-a","b-c","d-c", "c-d"}; 

    public void search(){ 
     TreeSet<String> res = new TreeSet<String>(); 
     for (String pair : myList) { 
      String[] splitted = pair.split("-"); 
      int findedCharFrom = (int)splitted[0].charAt(0); 
      int findedCharTo = (int)splitted[1].charAt(0); 

      String searchCombination = ""; 
      if(findedCharFrom < findedCharTo){ 
       for (int i = findedCharFrom+1 ; i <= findedCharTo; i ++) { 
        searchCombination += "" + (char) i; 
       } 
      }else{ 
       for (int i = findedCharFrom-1 ; i >= findedCharTo; i--) { 
        searchCombination += "" + (char) i; 
       } 
      } 

      TreeSet<String> tmpRes = new TreeSet<String>(); 
      for (String sub : getAllSub(searchCombination)) { 
       int n = sub.length(); 
       tmpRes.addAll(permute(sub, 0, n-1)); 
      } 

      for (String string : tmpRes) { 
       res.add((char)findedCharFrom +""+string+""+(char)findedCharFrom); 
      } 

     } 
     for (String string : res) { 
      System.out.println(string); 
     } 
    } 

    private TreeSet<String> getAllSub(String str){ 
     TreeSet<String> allSubs = new TreeSet<String>(); 
     for(int i=0;i<str.length();i++){ 
      allSubs.add(str.substring(i)); 
      for(int j=i;j<str.length();j++){ 
       if(j>i){ 
        allSubs.add(str.substring(i,j)); 
        String res = str.substring(i,j-1) + str.substring(j,str.length()); 
        if(!res.equals("")) 
         allSubs.add(res); 
       } 
      } 
     } 
     return allSubs; 
    } 
    private TreeSet<String> permute(String str, int l, int r) 
    { 
     TreeSet<String> res = new TreeSet<String>(); 
     if (l == r) 
      res.add(str); 
     else 
     { 
      for (int i = l; i <= r; i++) 
      { 
       str = swap(str,l,i); 
       res.addAll(permute(str, l+1, r)); 
       str = swap(str,l,i); 
      } 
     } 
     return res; 
    } 

    public String swap(String a, int i, int j) 
    { 
     char temp; 
     char[] charArray = a.toCharArray(); 
     temp = charArray[i] ; 
     charArray[i] = charArray[j]; 
     charArray[j] = temp; 
     return String.valueOf(charArray); 
    } 


    public static void main(String[] args) 
    { 
     TestRecursiveResearch permutation = new TestRecursiveResearch(); 
     permutation.search(); 
    } 
} 

而对于结果：

aba 
abca 
abcda 
abda 
abdca 
aca 
acba 
acbda 
acda 
acdba 
ada 
adba 
adbca 
adca 
adcba 
bab 
bcb 
cdc 
dcd