Récursivité - sous-ensembles - C++

Question

Merci @Scotty, @paddy. Pour votre information, la solution est la suivante:

void RecSubsets(string soFar, string rest) { 
    if (rest == "") { 
     cout << soFar << end; 
    } 
    else { 
     RecSubsets(soFar + rest[0], rest.substr(1)); 
     RecSubsets(soFar, rest.substr(1)); 
    } 
} 

void CanMakeSum(string set) { 
    RecSubsets("", set); 
} 

---

J'écris un programme simple pour calculer toutes les combinaisons possibles dans un ensemble en divisant les données en 2 sets (C (n-1, k-1 & C (n-1, k)) et appelant la fonction récursivement. Voici ce que j'ai écrit:

void RecSubsets(string soFar, string rest) { 
    if (rest == "") cout << soFar << end; 
    } 
    else { 
     for (int i = 0; i < rest.length(); i++) { 
      string next = soFar + rest[i]; 
      string remaining = rest.substr(i+1); 
      RecSubsets(next, remaining); 
     } 
    } 
} 

void CanMakeSum(string set) { 
    RecSubsets("", set); 
    RecSubsets("", set.substr(1)); 
} 

int main() {  
    string set = "abcd"; 
    CanMakeSum(set); 
    return 0; 
} 

Donc, pour une chaîne d'entrée « abcd », il serait divisé en 2 groupes (ABCD et abc), puis imprimer les combinaisons en appelant la fonction récursive. Sous cette logique, la sortie doit être: abcd, abc, abd, ab, acd, ac, ad, a ... Cependant, en utilisant le programme ci-dessus, la sortie est abcd, abd, acd, ad ... Je comprends conceptuellement ce que j'essaie de réaliser, mais j'ai du mal à le traduire en codes. Quelqu'un peut-il indiquer où je vais mal? Merci

Answer 1

C'est une bonne tentative. Il y a juste deux petits problèmes:

1. Vous devriez pas être "diviser les données en deux ensembles (C (n-1, k-1) & C (n-1, k))". Voilà à quoi sert votre fonction récursive!

2. RecSubsets() devrait toujours impression sur soFar. Supprimez le if (rest == "").

Par exemple:

void RecSubsets(string soFar, string rest) { 
    // First print out "a" or wherever we are up to 
    // This ensures we correctly get "ab" and "ac" without trailing characters etc 
    cout << soFar << end; 

    // Now print out the other combinations that begin with soFar 
    // This part of your algorithm was already correct :) 
    for (int i = 0; i < rest.length(); i++) { 
     string next = soFar + rest[i]; 
     string remaining = rest.substr(i+1); 
     RecSubsets(next, remaining); 
    } 
} 

void CanMakeSum(string set) 
{ 
    RecSubsets("", set); 
    // Don't call it a second time here 
} 

Answer 2

Vous voulez imprimer les résultats en post-ordre plutôt que pré-commande. L'autre réponse est presque correcte, mais vous l'avez rejetée trop facilement. Il ne fait pas de permutation car il n'y a pas de réordonnancement de la chaîne.

Le bon code de sortie des données dans l'ordre dont vous avez besoin est ceci:

void RecSubsets(string soFar, string rest) { 
    for (int i = 0; i < rest.length(); i++) { 
     string next = soFar + rest[i]; 
     string remaining = rest.substr(i+1); 
     RecSubsets(next, remaining); 
    } 
    if(soFar.size() > 0) cout << soFar << endl; 
} 

Sortie:

abcd 
abc 
abd 
ab 
acd 
ac 
ad 
a 
bcd 
bc 
bd 
b 
cd 
c 
d 
bcd 
bc 
bd 
b 
cd 
c 
d