Java - Trouver tous les chemins possibles en fonction des paires de clés tableau

Question

Je dispose d'un tableau de plusieurs paires de clés et je veux trouver tous les chemins possibles d'un élément et revenir par exemple:

array { 

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

} 

Je suis faire quelques boucles foreach mais je suis bloqué donné l'ensemble de données. Existe-t-il une meilleure façon de le faire ?

C'est ce que je l'ai fait:

1) Séparer toutes les clés

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

2) boucles Foreach et trouver son chemin immédiat, par exemple:

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

3) Je suis coincé ici

ab, maintenant de b - il y a beaucoup de chemins différents qu'il peut prendre et je ne sais pas comment o imbriqués pour chacun pour tous les différents chemins possibles.

Toute aide serait grandement appréciée

Qu'est-ce que je prévois:

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

Vous pourriez faire une boucle qui continue jusqu'à ce que tous les chemins commencent et se terminent par le même nœud. C'est à dire. vous commencez avec une liste d'un seul chemin contenant uniquement le noeud de départ. Pour chacun de ses voisins, copiez le chemin, ajoutez le voisin et ajoutez-le à la liste. Répétez jusqu'à ce que tous les chemins de la liste commencent et se terminent avec le même nœud.

Vous aurez également besoin d'une vérification pour éviter les boucles infinies.

Answer 2

La solution la plus simple consiste à énumérer tous les chemins possibles à partir des paires de nœuds données. Je suis sûr que j'oublie certains cas, mais cela devrait être réalisable à l'intérieur d'une seule boucle qui traverse les paires + quelques opérations de nettoyage:

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

Après cela, vous devriez avoir une liste des chemins du genre:

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

Ce qui est plus facile à vérifier pour votre condition prévue.

Ceci n'est pas optimal sur le plan informatique, mais devrait constituer un bon point de départ.

Answer 3

Vous pouvez regarder cette classe et la tester. Ce n'est pas la façon la plus propre de le faire, mais je suppose que c'est un début.

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(); 
    } 
} 

Et pour résultat:

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