Toutes Combinaisons de sous-chaînes dans une phrase en Java

Question

J'ai besoin de trouver les combinaisons de mots dans une chaîne séparée par des espaces. Supposons que la chaîne est "je vais", la sortie sera -

1. oui, je, aller
2. I, vais
3. je, vais

chaîne peut être plus . J'ai essayé mais bloqué. Voulez-vous s'il vous plaît m'aider à résoudre le problème. Merci d'avance.

public class Combination_Of_Words_In_Sentence { 

public static void main(String[] args) { 
    String inputString = "I will go"; 
    String[] arrString = inputString.split(" "); 
    printString(arrString); 
} 

private static void printString(String[] arrString) { 
    int len = arrString.length; 
    String[] arr = new String[len]; 

    for(int i=0;i<arrString.length;i++){ 
     for(int j=0;j<i+1;j++){ 
      arr[i] = arrString[j]+" "; 
      System.out.println(); 
     } 
     arr[i] +=","; 
     printPatternUtil(arrString, arr, 1, 1, len); 
    } 
} 

private static void printPatternUtil(String[] arrString, String[] arr, 
     int i, int j, int n) { 
    if(i == n){ 
     // arr[j] = " "; 
     for(int k=0;k<arr.length;k++) 
     System.out.print(arr[k]); 

     System.out.println(); 
      return; 
    } 
    arr[j] = arrString[i]+","; 
    printPatternUtil(arrString, arr, i+1, j+1, n) ; 

    // Or put a space followed by next character 
    // arr[j] = ","; 
    //arr[j+1] = arrString[i]+ " "; 

    // printPatternUtil(arrString, arr, i+1, j+2, n); 

} 

} 

Answer 1

Je voudrais suggérer que vous utilisiez une solution binaire, pour éviter d'avoir besoin de récursion. Vous pouvez compter, en binaire, le nombre de combinaisons dont vous avez besoin. Par exemple, avec deux mots, vous avez besoin d'une virgule. Avec trois mots, vous avez besoin de deux virgules. Donc, nombre de virgules = nombre de mots - 1.

Nous pouvons représenter les virgules avec des bits dans un compteur.

• Première virgule = bit 0
• Seconde virgule = bit 1
• Troisième bit virgule = 2
• etc ...

Ainsi, pour deux virgules, nous avons besoin de 2 bits . Les combinaisons possibles avec 2 bits est:

• 0B00 = 0
• 0B01 = 1
• 0b10 = 2
• 0b11 = 3

Pour trois virgules, les combinaisons possibles sont 0b000 = 0, 0b001 = 1, 0b010 = 2, 0b011 = 3, 0b100 = 4, 0b101 = 5, 0b110 = 6 et 0b111 = 7

Donc, pour deux comm Comme, vous avez juste besoin de compter de 0 (0b00) à 3 (0b11) et de tester chaque bit pour voir si vous avez besoin d'insérer une virgule. Pour trois virgules, comptez de 0 (0b000) à 7 (0b111).

Ceci est facile à calculer. Pour 2 virgules, prendre 2 à la puissance 2 = 4. Pour 3 virgules, prendre 2 à la puissance 3 = 8.

String[] words = {...}; 
int wordcount = words.length; 
int commacount = wordcount - 1; 
// Calculate the highest number to count to, in our loop 
int looplimit = 1 << commacount; // Same as 2 to the power commacount; 
for(int i=0;i<looplimit;i++) 
{ 
    // Start this phrase version with the first word. 
    String result = words[0]; 

    // Add the rest of the words, optionally adding commas. 
    // We've already added a word, so only count to wordcount-1 
    for(int j = 0; j<wordcount-1;j++) 
    { 
     // For word j, test the loop counter (i) to see if bit j is set. 
     boolean needComma = (i & (1 << j)) != 0; 

     // Add a comma or a space to this phrase version 
     result += needComma ? "," : " "; 

     // Add this word to the phrase version 
     result += words[j+1]; 
    } 
    System.out.println(result); 
}