Création de tableaux pour les permutations dans un paragraphe d'une liste

Question

J'ai une liste:

a 25 
b 18 
c 18 
d 18 
e 14 
f 14 
g 12 
... and so on 

Pour chaque numéro correspondant, je dois obtenir toutes les permutations de l'identifiant. Les listes dont je aurais besoin de mon exemple serait la suivante:

abcdefg 
abdcefg 
acbdefg 
acdbefg 
adbcefg 
adcbefg 
abcdfeg 
abdcfeg 
acbdfeg 
acdbfeg 
adbcfeg 
adcbfeg 

Étapes Je suis actuellement à résoudre le problème:

1. Lire dans la liste, placez chaque valeur dans un tableau ([a ] [12]) et placez cela dans une ArrayList
2. Je trouve alors s'il y a des nombres récurrents et en fais la note dans un HashMap
3. J'ai alors une boucle for configurée pour passer par la HashMap. Si le numéro ne s'est pas répété, je l'ajoute juste à la liste. Si le nombre a répété, j'utilise l'algorithme de Heap pour obtenir toutes les permutations.

Si je devais travailler à travers elle, j'ajouterions les numéros à une liste comme ceci:

a 
abcd 
abdc 
adbc 
... 
abcdef 
abcdfe 
abdcef 
adbcfe 
... 
abcdefg 
abcdfeg 

Mon code actuel ne fonctionne pas comme prévu (génère une seule liste) et je Je ne sais même pas comment commencer à écrire un code qui générerait continuellement de nouvelles listes, tout en ajoutant les anciennes listes. Je m'excuse d'être perdu, je suis dans un cours sur les structures de données en ce moment et tout se sent hors de ma zone de familiarité (nous avons juste commencé à discuter des listes liées).

Note 1: allLists contient toutes les listes actuelles (a, abcd, adcb,) et permutationList contient toutes les permutations de la liste.

Note 2: Je fais cela à travers une liste booléenne, mais utilisé les lettres comme une représentation visuelle facile pour ce que je suis en train d'accomplir

code où je pense que le problème est:

public static Boolean[] combine (int i, int j) { 
    int aLen = allLists.get(j).length; 
    int bLen = permutationList.get(i).length; 

    Boolean[] newList = new Boolean[aLen + bLen]; 
    System.arraycopy(allLists.get(j), 0, newList, 0, aLen); 
    System.arraycopy(permutationList.get(i), 0, newList, aLen, bLen); 

    return newList; 
} 

public static void setAllLists() { 
    if(allLists.size() == 0) { 
     allLists.add(permutationList.get(0)); 
    } 

    for(int i = 0; i < permutationList.size(); i++) { 
      for(int j = 0; j < allLists.size(); j++) { 
       Boolean[] newList = combine(i,j); 
       if(i == 0) { 
        allLists.set(j, newList); 
       } 
       else { 
        allLists.add(newList); 
      } 
     } 
    } 
    permutationList.clear(); 
} 

Answer 1

Hypothèses:
Je ne connais pas votre format d'entrée, mais je suppose que j'ont ai deux listes alphabets qui ont la liste des alphabets et values qui ont la liste des valeurs correspondantes. Les deux sont égaux en longueur et values sont en ordre décroissant.

Voilà mon approche du problème:

1. Convertir l'entrée à un Map<Integer, List<String>> valuesToListMap = new TreeMap<>(Collections.reverseOrder());. Pourquoi? Parce que cette carte dira les sous-chaînes que je devrais trouver des permutations pour (dans votre exemple, ce serait {a},{b,c,d},{e,f},{g} et comme la carte est de type TreeMap et les entrées dans ce sera en ordre naturel inverse (décroissant), je peux assurer la 18 -> {b,c,d}
2. Ensuite, je passerai en revue les valeurs du valuesToListMap. Je trouverai les permutations de chaque liste. être {{a},{bcd,bdc,cbd,cdb,dbc,dcb},{ef,fe},{g} Appelons cette collection permutationsList
3. Ensuite, je vais parcourir les deux entrées à la fois permutationsList et commencer à ajouter chaque élément de première entrée avec chaque élément de deuxième entrée.Par exemple, j'ajouterai chaque élément de l'entrée {a} au permutationsList avec chaque élément de l'entrée {bcd,bdc,cbd,cdb,dbc,dcb}. Donc, ma sortie après la fusion sera {abcd,abdc,acbd,acdb,adbc,adcb}
4. Continuer à faire l'étape 3 récursive et vous devriez avoir votre sortie

Quelques notes:
L'utilisation TreeMap assure que nous ne disposons pas d'une sortie bcdaefg parce que c'est pas dans l'ordre décroissant des valeurs.

Ma solution est ci-dessous. Je ne l'ai pas fait toute validation d'entrée ou de contrôles de sanité, mais cela devrait être facile à faire:

public class PermutationWithinSubsection { 
public static void main(String[] args) { 
    List<String> alphabets = Arrays.asList("a","b","c","d","e","f","g"); 
    List<Integer> values = Arrays.asList(25,18,18,18,14,14,12); 
    // Step 1 start 
    Map<Integer, List<String>> valuesToListMap = new TreeMap<>(Collections.reverseOrder()); // Order the map in reverse order of values 
    for(int i=0; i<alphabets.size(); i++) { 
     if(valuesToListMap.containsKey(values.get(i))) { 
      List<String> temp = valuesToListMap.get(values.get(i)); 
      temp.add(alphabets.get(i)); 
      valuesToListMap.put(values.get(i),temp); 
     } else { 
      List<String> temp = new ArrayList<>(); 
      temp.add(alphabets.get(i)); 
      valuesToListMap.put(values.get(i), temp); 
     } 
    } 
    // Step 1 end 

    // Step 2 start 
    List<List<String>> permutationsList = new ArrayList<>(); 
    for(List<String> ip: valuesToListMap.values()) { 
     List<String> result = new PermutationWithinSubsection().permute(ip); 
     permutationsList.add(result); 
    } 
    // Step 2 end 

    // // Step 3 start 
    int count = 1; 
    List<String> l1 = permutationsList.get(0); 
    List<String> r = new PermutationWithinSubsection().merge(l1, permutationsList, count); 
    // // Step 3 end 
    System.out.println("r = " + r); 
} 

/** 
* Find permutations of input list using backtracking 
* @param ip 
* @return 
*/ 
private List<String> permute(List<String> ip) { 
    List<String> list = new ArrayList<>(); 
    backtrack(list, new ArrayList<>(), ip); 
    return list; 
} 

private void backtrack(List<String> list, ArrayList<String> tempList, List<String> nums) { 
    if(tempList.size() == nums.size()){ 
     StringBuilder sb = new StringBuilder(); 
     for(String s: tempList) { 
      sb.append(s); 
     } 
     list.add(sb.toString()); 
    } else{ 
     for(int i = 0; i < nums.size(); i++){ 
      if(tempList.contains(nums.get(i))) continue; // element already exists, skip 
      tempList.add(nums.get(i)); 
      backtrack(list, tempList, nums); 
      tempList.remove(tempList.size() - 1); 
     } 
    } 
} 


/** 
* Keep on merging lists till we have merged all 
* @param l1 
* @param resultLists 
* @param count 
* @return 
*/ 
private List<String> merge(List<String> l1, List<List<String>> resultLists, int count) { 
    if(count == resultLists.size()) { 
     return l1; 
    } 
    List<String> l2 = resultLists.get(count); 
    List<String> f = new ArrayList<>(); 
    for(String s1: l1) { 
     for(String s2: l2) { 
      f.add(s1+s2); 
     } 
    } 
    return merge(f,resultLists,++count); 
} 

}

Sortie: r = [abcdefg, abcdfeg, abdcefg, abdcfeg, acbdefg, acbdfeg, acdbefg, acdbfeg, adbcefg, adbcfeg, adcbefg, adcbfeg]

espère que mon explication était claire. Faites moi savoir si vous avez des questions.