Infinite Récursion pour trouver les sous-ensembles d'une chaîne?

Question

J'essaie de trouver tous les sous-ensembles d'une chaîne donnée. Par exemple, la chaîne "Rum" aurait les sous-ensembles "rhum", "ru", "rm", "r", "um", "u", "m", et "". Voici mon code à ce jour:

import java.util.Collections; 
import java.util.ArrayList; 
import java.util.List; 
public class SubsetGenerator 
{ 
    private String word; 

    public SubsetGenerator(String in) 
    { 
     word=in; 
    } 
    public ArrayList<String> findSubsets() 
    { 
     ArrayList<String> subsets = new ArrayList<String>(); 
     String temp = word; 
     if(temp.length()==1) 
     { 
      subsets.add(temp); 
      return subsets; 
     } 
     else 
     { 
      String removed = temp.substring(0,1); 
      temp = temp.substring(1); 
      findSubsets(); 
      subsets.add(word); 
     } 
     return subsets; 
    } 

} 

et voici le testeur:

import java.util.Collections; 
import java.util.ArrayList; 
import java.util.List; 
/** 
This program tests the subset generator. 
*/ 
public class SubsetGeneratorTester 
{ 
public static void main(String[] args) 
{ 
SubsetGenerator generator = new SubsetGenerator("rum"); 

List<String> subsets = generator.findSubsets(); 
// Sort the result for checking 
Collections.sort(subsets); 
System.out.println(subsets); 
System.out.println("Expected: [, m, r, rm, ru, rum, u, um]"); 
} 
} 

Answer 1

Votre méthode est quelque peu déroutant. Je suggère que vous utilisiez un algorithme semblable à ceci:

public class SubsetGenerator { 
    private String word; 
    private ArrayList<String> list; 

    public SubsetGenerator(String word) { 
     //constructor and initialize variables 
    } 

    void findSubsets(String str) { 
     list.add(str) 

     for(int i = 0 ; i < str.length() ; i++) { 
      String substring = /*str with char at index i removed*/ 
      this.findSubsets(substring); 
     } 
    } 
} 

cela devrait inclure tous les variants. J'espère que cela aide.

Answer 2

J'ai écrit une solution de retour en arrière récursif:

import java.util.Collections; 
import java.util.ArrayList; 
import java.util.List; 
public class SubsetGenerator 
{ 
    private String word; 
    private ArrayList<String> temp; 

    public SubsetGenerator(String in) 
    { 
     word=in; 
     temp = new ArrayList<String>(); 
    } 
    public void solve(int idx, String s){ 
     if(idx == word.length()){ 
      temp.add(s); 
      return; 
     } 
     solve(idx+1, s + word.charAt(idx)); 
     solve(idx+1, s); 
    } 
    public ArrayList<String> findSubsets(){ 
     solve(0, ""); 
     return temp; 
    } 
}