Bei 3 eindeutigen Buchstaben: Können Sie die sechs möglichen nicht wiederholenden Kombinationen der Buchstaben mithilfe einer rekursiven Funktion drucken? 'cat' sollte Folgendes ausgeben: cat, act, atc, tac, tca und cta. Hier ist mein Programm. Ich habe Probleme, den rekursiven Algorithmus zu finden. Hier ist mein Versuch:

 static void findWords(StringBuilder string, int start, int stride) {
    //1. iterate through all possible combinations of the chars recursively

    System.out.println(string);

    if (stride < string.length() && start < string.length())
    {
        char temp = string.charAt(stride);
        string.setCharAt(stride, string.charAt(start));
        string.setCharAt(start, temp);

        findWords(string, start, stride + 1);

        findWords(string, start + 1, stride + 1 );


    }
}

public static void main(String[] args)
{

   StringBuilder word = new StringBuilder("cat");
   findWords(word,0,1);
}
1
MGT 24 Juni 2018 im 00:51

3 Antworten

Beste Antwort

Lösung:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static List<String> resultList = new ArrayList<>();

    static void computeResult(char[] s, int pos, String resultString) {
        if (pos == 3) {
            resultList.add(resultString);
            return;
        }
        for (int i = 0; i < 3; ++i) {
            if (!resultString.contains(String.valueOf(s[i]))) {
                computeResult(s, pos + 1, resultString + s[i]);
            }
        }
    }

    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();
        computeResult(s, 0, "");
        for(String str : resultList) {
            System.out.println(str);
        }
    }
}

Erläuterung:

Die Rekursion erfolgt über die Funktion computeResult. Es beginnt mit einer leeren Zeichenfolge, durchläuft dann alle möglichen Buchstaben 'c', 'a' und 't' und hängt sie an den resultString an. Jetzt gibt es 3 Zeichenfolgen und für jede von ihnen die Funktion computeResult wird erneut aufgerufen. Dann macht es dasselbe und fügt dem resultString nur die Buchstaben hinzu, die noch nicht hinzugefügt wurden. An 'c' hängen wir also 'a' an, was zu 'ca' und 't' führt, was zu 'ct', I führt Denken Sie, den Rest können Sie selbst herausfinden.

Beachten Sie, dass dies funktioniert, wenn die Buchstaben eindeutig sind. Wenn dies nicht der Fall ist, erhalten Sie beispielsweise die Zeichenfolge 'tat'. Sie können sie in t1a1t2 umwandeln und das gleiche Verfahren für das Array ['t1', 'a1', 't2'] ausführen. Entfernen Sie dann die Ziffern.

1
Coder-Man 23 Juni 2018 im 22:13

Der von mir verwendete Algorithmus ist recht einfach. Machen Sie jedes Zeichen zum ersten Zeichen der Zeichenfolge und finden Sie Kombinationen mit anderen zwei Zeichen. Für die Zeichen c, a, t wären also die Kombinationen

c at
c ta

a ct
a tc

t ca
t ac

Code:

static void findWords(String str, int pos) {
    if(str == null || pos < -1) {
        return;
    }

    int len = str.length();
    if(pos + 1 < len) {
        findWords(str, pos + 1);
    }

    //find char swap positions
    int pos1 = (pos + 1) % len;
    int pos2 = (pos - 1 + len) % len;

    char[] chars = str.toCharArray();
    String str1 = new String(new char[] {chars[pos], chars[pos1], chars[pos2]});
    String str2 = new String(new char[] {chars[pos], chars[pos2], chars[pos1]});

    System.out.println(str1);
    System.out.println(str2);
}

public static void main(String[] args) {
    String word = new String("abc");
    findWords(word, 0);
}
1
javamusings 24 Juni 2018 im 00:05

Hier ist ein voll funktionsfähiges Beispiel mit meinen Kommentaren zur Erläuterung des Algorithmus.

Diese Lösung basiert auf Backtracking. Lesen Sie hier mehr darüber . Betrachten Sie das Problem als Baum. In Ihrem Beispiel lautet das Wort "Katze". Hier kommt etwas ASCII-Kunst ...

                                      cat
                              /        |        \
                            Cat       Act       Tca 
                           /   \     /   \     /   \
                          CAt CTa   ACt ATc   TCa TAc

Bei jedem Durchgang fixieren Sie einen Brief (ich habe ihn als Großbuchstaben angegeben). Je weiter unten im Baum, desto weniger können Sie tauschen, da Sie eine bestimmte Anzahl von Buchstaben festgelegt haben (auf Stufe 0 ist nichts festgelegt, auf Stufe 1 ist ein Buchstabe festgelegt, sodass ein Tausch durchgeführt werden kann. Auf Stufe 2 haben Sie keine Swaps mehr (der Swap wäre bei sich selbst), sodass die Rekursion ihren Basisfall erreicht.

public static void main(String[] args) {
    // get all the permutations of a word with distinct letters
    Set<String> permutations = getPermutations("cat");

    // print the resulting set
    System.out.println(permutations);
}

private static Set<String> getPermutations(String string) {
    // recursive call to get a permutation of the given string and put it in
    // the set of permutations (initially empty)
    return permute(string, 0, string.length() - 1, new HashSet<String>());
}

private static Set<String> permute(String string, int left, int right, Set<String> set) {
    if (left == right) {
        // swap would be with itself so just add the string
        // this is the base case
        set.add(string);
    } else {
        for (int i = left; i <= right; i++) {
            // indices are different, something can be swapped so swap it
            string = swap(string, left, i);
            // permute the swapped string starting from the next available character
            permute(string, left + 1, right, set);
        }
    }
    return set;
}

// utility method to carry out the swapping
// you could do this with primitive char[] and probably improve performance
// but for the sake of simplicity as it's just an exercise I used a 
// StringBuilder
private static String swap(String in, int i, int j) {
    char tmp1 = in.charAt(i);
    char tmp2 = in.charAt(j);
    StringBuilder sb = new StringBuilder(in);
    // put the char at j in place of the char at i
    sb.setCharAt(i, tmp2);
    // and do the same the other way around
    sb.setCharAt(j, tmp1);

    return sb.toString();
}
0
William Burnham 24 Juni 2018 im 00:01