Un petit problème de récurrence en Java

Question

Je suis actuellement en train de travailler sur des problèmes de récursion, et je suis actuellement bloqué sur un.

Le problème consiste à insérer récursivement des espaces dans une chaîne de caractères, à tous les endroits possibles, de sorte que la sortie ressemble à quelque chose comme.. :

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D
       A BC D
       AB CD
       AB C D
       ABC D

J'ai actuellement travaillé sur le problème, et je suis arrivé à un point semblable :

Input: ABCD
Out:
       ABCD
       A BCD
       A B CD
       A B C D

Mon code pour le problème jusqu'à présent :

import java.util.Scanner;

public class Words 
{
    static int counter = 0;
    static String fString = "";
    static String fString2 = "";
    static String previous = "";
    static String input = "";
    static String other = "";

    public static String segment(String inputPrefix, String restOfString)
{
    if(restOfString.length() != 0)
    {   
        if(inputPrefix.equals(""))
        {
            fString += restOfString + "\n";
            segment(restOfString.substring(0,1), restOfString.substring(1));
        }
        else
        {
            previous += inputPrefix + " ";
            fString += previous + restOfString + "\n";
            fString2 = previous + restOfString;
            segment(restOfString.substring(0,1)
                            , restOfString.substring(1));
        }
    }
    /*else
    {
        counter++;
        other = fString2.replaceAll(" ", "");
        System.out.println(other);
        if((counter + 1) < other.length())
        {
            System.out.println("Other: " + other);
            input = other.substring(0, counter + 1);
            other = other.substring(counter + 1);
            System.out.println(counter);
            System.out.println("input: " + input);
            System.out.print("other: " + other);

            segment(input, other);
        }
        else
            return fString;
    }*/

    return fString;

}

public static void main (String[] args) 
{
    Scanner scan = new Scanner(System.in);
    System.out.print("Enter a string: ");
    String input = scan.next();
    System.out.println();
    System.out.println(segment("", input));

}
}

La deuxième clause else est celle qui me pose le plus de problèmes, car chaque fois que je l'exécute sans la compléter, elle se transforme en une boucle infinie. J'ai même mis des instructions int trace (les println ) et cela n'aide toujours pas.

Je l'ai lu plusieurs fois et je ne comprends pas pourquoi cela ne fonctionne pas.

Answer 1

La première chose qui me fait douter de votre code est que vous êtes censé retourner une série de chaînes de caractères, mais votre valeur de retour est une chaîne de caractères.

Vous devriez peut-être préciser votre cas de base et votre étape récursive.

On dirait que vous avez un début de scénario de base. Vous pouvez insérer zéro espace dans la chaîne vide, donc

allPossibleSpacings("") -> [ "" ]

mais vous ne voulez pas insérer un espace à la fin, donc vous avez besoin d'un deuxième cas de base

allPossibleSpacings("x") -> [ "x" ]

et ensuite votre étape récursive pourrait être

allPossibleSpacings("x" + s) -> flatten(
    ∀ t : allPossibleSpacings(s), ["x" + t, "x " + t])

Je ne vous aiderai pas à écrire cela en Java puisque c'est un devoir, mais j'espère que cela vous aidera.

Answer 2

void recurse(String myString, int start){
        System.out.println(myString);
        for(int i = start; i < myString.length; i++) {
            if (myString.charAt(i) != ' ' ){
                recurse(myString.Substring(0,i) + ' ' + myString.Substring(i), i+2);
            }
        }
    }

appeler en premier lieu avec recurse("ABCD", 1) ;

Answer 3

Il semble que vous ayez réussi à effectuer le premier "regroupement" correctement, mais que vous ne parveniez pas à obtenir les regroupements suivants.

Les groupements sont : "A BCD", "AB CD" et "ABC D". Vous devez appliquer votre algorithme à chacun de ces groupements. Vous l'avez appliqué au premier. Comment obtenir les autres ?

Est-ce que suffisamment de temps a passé ? J'ai écrit une solution en python juste pour voir ce que ça donnerait par rapport à Java.

def segment(input, separator=' ', start_from=0):
    print input
    # add spaces after each letter starting from start_from index, terminating at last letter-1
    for i in range(start_from, len(input)-1):
        # if the next letter is already a space, or this letter is a space, move on
        if separator in (input[i+1], input[i]): continue
        # whatever index we're on, do the next one recursively
        segment(input[:i] + input[i] + separator + input[i+1:], separator=separator, start_from=i+1)

segment('ABCD')