Substrings finden

[Secretdeadlyallo]

Hallo, habe folgendes Problem:
Ich möchte als Eingabe in der Konsole einen String und eine Zahl. Danach rekursiv alle möglichen Teilsequenzen davon finden.

Habe folgendes überlegt:

import java.util.Scanner;
public class Teilfolgen {
 public static int num;
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  System.out.println("enter a string");
  String input = sc.next();
  System.out.println("enter a non negative integer");
  num = sc.nextInt();
  if (num < 0) {
   System.out.println("incorrect input");
  }
  findeTeilfolgen(input);
 }
 public static void findeTeilfolgen(String input) {
  if (num == input.length()) {
   System.out.println(input);
  } else {   
   findeTeilfolgen(input.substring(0, input.length() - 1));
   findeTeilfolgen(input.substring(1, input.length()));
  }
 }
}

Wenn ich nun jedoch als Input "Hund" nehme mit num = 2 sollte ich ja bekommen:
hu hn hd un ud nd
Jedoch erhalte ich nur:
hu un un nd

Ich geh davon aus, dass bei den rekursiven Aufrufen bei input.substring die 2 Parameter noch falsch sind, komme jedoch nicht drauf wie ich mein Programm änderen muss um es korrekt zu bekommen.

 

[Tarrew]

Wenn ich nun jedoch als Input "Hund" nehme mit num = 2 sollte ich ja bekommen:
hu hn hd un ud nd

Sicher, dass du Substrings finden möchtest? "hn", "hd" und "ud" sind keine Substrings von "Hund".

Kann das sein, dass du eher alle Permutationen der Buchstaben "h", "u", "n" und "d" mit der Länge 2 suchst?
Dann fehlen in der Aufzählung wiederum einige. Oder alle Potenzmengen mit 2 Buchstaben, ohne die Reihenfolge zu verändern?

Vllt. nochmal etwas genauer beschreiben, was genau das Ziel sein soll.

 

[Secretdeadlyallo]

Also bei z.b. num = 2 und String "Hund" will ich:
Buchstabe 1 + Buchstabe 2
Buchstabe 1 + Buchstabe 3
Buchstabe 1 + Buchstabe 4
Buchstabe 2 + Buchstabe 3
Buchstabe 2 + Buchstabe 4
Buchstabe 3 + Buchstabe 4

 

[Tarrew]

   findeTeilfolgen(input.substring(0, input.length() - 1));
   findeTeilfolgen(input.substring(1, input.length()));

Ich glaube mit der substring-Methode kann das allgemein nicht klappen, da du nie Teilmengen erwischen wirst, bei denen die Buchstaben nicht direkt hintereinander liegen.

Wenn man die ganze Methode etwas erweitert und in einem boolean-Array "mittrackt" welchen Buchstaben an welchem Index man schon "abgearbeitet" hat, dann könnte das so aussehen:

    public static void main(String[] args) {
        char[] arr = "Hund".toCharArray();
        teilmenge(arr, 0, new boolean[arr.length], 2);
    }

    public static void teilmenge(char[] input, int index, boolean[] covered, int num) {
        if (index == covered.length) {
            if (countBoolean(covered, true) == num) {
                for (int i = 0; i < covered.length; i++) {
                    if (covered[i]) {
                        System.out.print(input[i]);
                    }
                }
                System.out.println();
            }
        } else {
            teilmenge(input, index + 1, covered, num);
            covered[index] = true;
            teilmenge(input, index + 1, covered, num);
            covered[index] = false;
        }
    }

    private static int countBoolean(boolean[] arr, boolean b) {
        int count = 0;

        for (boolean ab : arr) {
            count += ab == b ? 1 : 0;
        }
        return count;
    }

Vllt. hat aber jemand anderes auch eine etwas elegantere Lösung 😉


Mit externen Bibliotheken (Guava) geht das auch etwas kürzer (ggf. noch Sortierung der Indizes beachten):

    public static void main(String[] args) {
        char[] arr = "Hund".toCharArray();
        int num = 2;

        Set<Set<Integer>> powerSet = Sets.powerSet(IntStream.range(0, arr.length).boxed().collect(Collectors.toSet()))
                .stream()
                .filter(s -> s.size() == num)
                .collect(Collectors.toSet());

        for (Set<Integer> subSet : powerSet) {
            for (Integer charIndex : subSet) {
                System.out.print(arr[charIndex]);
            }
            System.out.println();
        }
    }

 

[max40]

public static void main(String[] args) {
    String s = "Hund";
    int len = 2;
    work(s.toCharArray(), new char[len], 0, 0);
}

static void work(char[] data, char[] cur, int ebene, int pos) {
    for (int i = pos, len = data.length - (cur.length - ebene - 1); i < len; i++) {
        cur[ebene] = data[i];
        if (ebene + 1 < cur.length) {
            work(data, cur, ebene + 1, i + 1);
        }else {
            System.out.println(Arrays.toString(cur));
        }
    }
}

 

[Secretdeadlyallo]

Danke euch beiden für die Hilfe.