Verschlüsselung mit replace()

[Miene1289]

Hallo zusammen

Ich versuche gerade ein Programm zu erstellen, was eingegeben Sätze verschlüsselt. So soll aus 'a' ein 'd' werden und aus einem 'd' ein 'g'.
Habs mit replace('a','d') und replace('d','g') versucht, leider wird danach auch jedes neue d (was vorher ein a war) als g ersetzt.
Z.B. soll aus Hand Hdng werden und nicht Hgng.

Gibt es dafür eine andere Methode, die ich verwenden kann? Danke in Voraus.

 

[abc66]

Nicht wirklich, das ist NP-vollständig...

Beispiel:
Aus a soll b werden,
aus b c
und aus c d.
Eingabe: abc.
Nun muss eine Reihenfolge für b,c,d gefunden werden, so dass diese auf abc hintereinanderausgeführt werden kann. Das ist nicht trivial. Eine mögliche wäre:
Ersetze alle c durch d, ersetze alle b durch c, ersetze alle a durch b.

 

[abc66]

Hier bitte

Spoiler

	static ArrayList<ArrayList<String>> a(String s, ArrayList<ArrayList<String>> l, ArrayList<ArrayList<String>> l2) {
		if (l.isEmpty()) {
			return l2;
		}
		for (int i = 0; i < l.size(); i++) {
			l2.add(l.remove(i));
			String s2 = s;
			for (int j = 0; j < l2.size(); j++) {
				s2 = s2.replaceAll(l2.get(j).get(0), l2.get(j).get(1));
			}
			for (int j = l2.size() - 1; j >= 0; j--) {
				s2 = s2.replaceAll(l2.get(j).get(1), l2.get(j).get(0));
			}
			if (s.equals(s2)) {
				ArrayList<ArrayList<String>> l3 = a(s, l, l2);
				if (l3 != null) {
					return l3;
				}
			}
			l.add(i, l2.remove(l2.size() - 1));
		}
		return null;
	}

	public static void main(String[] args) {
		String s = "hallo";
		ArrayList<ArrayList<String>> l = new ArrayList<ArrayList<String>>();
		l.add(new ArrayList<String>(List.of("h", "a")));
		l.add(new ArrayList<String>(List.of("a", "b")));
		l.add(new ArrayList<String>(List.of("l", "c")));
		l.add(new ArrayList<String>(List.of("o", "d")));
		ArrayList<ArrayList<String>> l3 = a(s, l, new ArrayList<ArrayList<String>>());
		System.out.println(l3);
		for (int i = 0; i < l3.size(); i++) {
			s = s.replaceAll(l3.get(i).get(0), l3.get(i).get(1));
		}
		System.out.println(s);
	}

 

[LimDul]

Die einfachste Variante wäre den String zeichenweise durchzugehen und zeichenweise zu ersetzen.

 

[abc66]

Das macht er doch schon, dabei tritt oben beschriebenes Problem auf...

 

[LimDul]

Nein, den zu verschlüsselnden String zeichenweise durchgehen und jedes Zeichen einzeln ersetzen. Also erst die erste Stelle des Strings ersetzen, dann die zweite usw.

 

[abc66]

Das ginge auch... er hat aber explizit nach "replaceAll()" gefragt.

 

[httpdigest]

das ist NP-vollständig...

Nein?! Das ist mit Sicherheit nicht NP-vollständig, also äquivalent zu einem NP-harten Problem, welches von einem nicht-deterministischen Algorithmus in polynomieller Zeit gelöst werden kann.
Du selbst hast ja einen deterministischen Algorithmus angegeben, der in polynomieller Zeit das Problem löst...
Das Problem selbst ist ja ziemlich identisch zum Berechnen des "dominance frontier" eines Graphen, der die Abhängigkeit einer Ersetzung zu einer anderen Ersetzung angibt. Und das kann man locker in polynomieller Zeit lösen, also sowohl den Abhängigkeitsgraph aufbauen als auch das Problem damit lösen.

 

[abc66]

Du selbst hast ja einen deterministischen Algorithmus angegeben, der in polynomieller Zeit das Problem löst...

Hmm, ist die Laufzeit denn nicht faktoriell, also n!? (Wobei n die Anzahl zu ersetzender Zeichen/Strings ist)?

 

[LimDul]

Das Problem bei diesen Lösungen, die klappen nur bei zyklenfreien Graphen.

Wenn ich a=>b ersetzen will und b=>a, dann klappt das nicht mehr. Dann muss ich entweder zeichenweise ersetzen oder auf Zeichen ausweichen, die weder im zu verschlüsselnden Text, noch in der Verschlüsselung auftauchen.

 

[abc66]

Das Problem selbst ist ja ziemlich identisch zum Berechnen des "dominance frontier" eines Graphen, der die Abhängigkeit einer Ersetzung zu einer anderen Ersetzung angibt. Und das kann man locker in polynomieller Zeit lösen, also sowohl den Abhängigkeitsgraph aufbauen als auch das Problem damit lösen.

Den angegebenen, "naiven" Algorithmus habe ich in 10 Minuten geschrieben - durchaus möglich, das er nicht perfekt ist.

 

[httpdigest]

Den angegebenen, "naiven" Algorithmus habe ich in 10 Minuten geschrieben - durchaus möglich, das er nicht perfekt ist.

Ich hab doch gar nichts an deinem Algorithmus ausgesetzt. Nur, dass das Problem eben nicht NP-hart ist, weil dein Algorithmus das ja sogar in polynomieller Zeit löst.

Hier noch eine Variante:

Spoiler

import static java.util.stream.Collectors.*;
import java.util.*;
public class RichtigErsetzen {
  public static String ersetzeRichtig(String str, Map<Character, Character> ersetzungen) {
    return str.chars()
        .mapToObj(c -> (char) c)
        .map(c -> ersetzungen.getOrDefault(c, c).toString())
        .collect(joining());
  }
  // Helper method to create a map with varargs
  private static Map<Character, Character> map(Character... keyAndValue) {
    Map<Character, Character> m = new HashMap<Character, Character>();
    for (int i = 0; i < keyAndValue.length; i += 2)
      m.put(keyAndValue[i], keyAndValue[i+1]);
    return m;
  }
  public static void main(String[] args) {
    System.out.println(ersetzeRichtig("abcdefg", map(
      'a', 'b',
      'b', 'c',
      'c', 'd',
      'd', 'e'
    )));
  }
}

 

[abc66]

Das Problem bei diesen Lösungen, die klappen nur bei zyklenfreien Graphen.

Auch das stimmt... Aber ich bin einfach davon ausgegangen, dass die Ersetzungen keine Zyklen enthalten.

Hier noch eine Variante:

Nach meiner Meinung, sucht er einfach eine Reihenfolge der Ersetzungen, mit der er replaceAll(...,ersetzung_i); aufrufen kann.

 

[abc66]

Ok, wann ist ein Algo np-vollständig? Wenn es einen Algo der eine optimale Lösung für das Problem findet gibt in einer Laufzeit von O(p(n)), wobei p(n) ein Polynom k-ten Grades von n ist.
2^n zählt doch zum Beispiel dazu?

 

[httpdigest]

wann ist ein Algo np-vollständig? Wenn es einen Algo der eine optimale Lösung für das Problem findet gibt in einer Laufzeit von O(p(n)), wobei p(n) ein Polynom k-ten Grades von n ist.

Nein. Ein Problem liegt in NP, wenn es einen nicht-deterministischen (das "N" in NP) Algorithmus gibt, der das Problem in polynomieller (das "P" in NP) Zeit lösen kann. Da man mit Computern aber nur deterministische Algorithmen abbilden kann, und man jeden nicht-deterministischen Algorithmus in einen deterministischen Algorithmus umwandeln kann, indem die Anzahl der Operationen mit `n` (der Eingabegröße) potenziert wird, kann man quasi sagen, dass NP Probleme solche sind, die in exponentieller (Problemgröße `n` steht im Exponent) Zeit lösbar sind. Zusätzlich ist ein Problem "A" in NP-hart, wenn jedes andere Problem in NP durch einen deterministisch polynomiellen Algorithmus in das Problem "A" konvertiert werden kann.

2^n zählt doch zum Beispiel dazu?

Welches Beispiel meinst du, und was meinst du mit "dazuzählen"?

 

[temi]

Nach meiner Meinung, sucht er einfach eine Reihenfolge der Ersetzungen, mit der er replaceAll(...,ersetzung_i); aufrufen kann.

Ähm, nö. Sie oder er möchte einfach ihr oder sein Problem lösen und replace() war nur ein Versuch ihrerseits oder seinerseits:

Ich versuche gerade ein Programm zu erstellen, was eingegeben Sätze verschlüsselt. [...] Habs mit replace('a','d') und replace('d','g') versucht [...] Gibt es dafür eine andere Methode, die ich verwenden kann?

Insofern ist der Ansatz von @LimDul nicht schlecht.

 

[abc66]

Welches Beispiel meinst du, und was meinst du mit "dazuzählen"?

O(2^n) polynomielles Wachstum und ein (nur) in dieser Zeit lösbares Problem wäre np-vollständig, oder nicht?

 

[abc66]

Ähm, nö. Sie oder er möchte einfach ihr oder sein Problem lösen und replace() war nur ein Versuch ihrerseits oder seinerseits

Dann lass es mich so formulieren, wenn sie oder er den (kleinsten) "allgemeinsten Unifikator" sucht, mit dessen Ausdrücken sie oder er mehrmals replaceAll(...); aufrufen kann, dann hab ich ne Methode dafür, die sie oder er nutzen kann.

 

[httpdigest]

O(2^n) polynomielles Wachstum und ein (nur) in dieser Zeit lösbares Problem wäre np-vollständig, oder nicht?

Also, 2^n ist keine polynomielle Funktion bezogen auf `n`, sondern exponentiell (`n` steht im Exponent).
Generall kann man nicht sagen, dass jedes Problem mit einer Zeitkomplexität von `2^n` auch in NP liegt. Hierfür ist eine weitere Bedingung notwendig: Eine Lösung des Problems kann deterministisch polynomiell verifiziert werden. Also: Gegeben das Problem und eine mögliche Lösung. Jetzt muss die Prüfung, ob dies auch eine gültige Lösung des Problems ist, in deterministisch polynomieller Zeit erfolgen (und nicht schneller).
Das umgekehrte gilt aber**, also: jedes Problem in NP hat deterministisch exponentielle Laufzeit zum Lösen des Problems.
Ob es auch NP-vollständig ist, wissen wir nur, wenn wir beweisen können, dass es auch NP-hart ist, also dass es einen deterministisch polynomiellen Algorithmus gibt, der jedes bisher bekannte Problen in NP auf dieses Problem reduzieren kann.

** zumindest solange das P-NP-Problem nicht gelöst ist

 

[abc66]

Jetzt muss die Prüfung, ob dies auch eine gültige Lösung des Problems ist, in deterministisch polynomieller Zeit erfolgen (und nicht schneller).

Die Prüfung einer Lösung, ob sie gültig ist, erfolgt bei mir aber in n... Also ist es wohl nicht np-"stark"...

 

[mihe7]

Jetzt muss die Prüfung, ob dies auch eine gültige Lösung des Problems ist, in deterministisch polynomieller Zeit erfolgen (und nicht schneller).

Wieso "und nicht schneller"?!?

Die Prüfung einer Lösung, ob sie gültig ist, erfolgt bei mir aber in n...

SZ ∈ O(n) wäre Polynomialzeit, denn es gibt ein k, nämlich k=1, so dass SZ ∈ O(n^k) gilt.

Die Klasse NP enthält die Probleme, die mit einer NTM in Polynomialzeit lösbar sind, das schließt alle Probleme ein, die mit einer DTM in Polynomialzeit lösbar sind. (P ⊆NP). Die Probleme der Klasse NP sind diejenigen, für die mit einer DTM in Polynomialzeit überprüft werden kann, ob eine gegebene Lösung gültig ist.

Das TSP ist bekanntermaßen NP-schwer.

Nun kann man fragen, ob es eine Rundreise gibt, die eine gegebene Länge nicht überschreitet. Dieses Entscheidungsproblem liegt in NP, denn jede Lösung kann mit einer DTM in Polynomialzeit (hier: linear) auf ihre Gültigkeit hin überprüft werden. Da das Problem nun NP-schwer ist und in NP liegt, ist es NP-vollständig.

Man kann aber auch nach der kürzesten Rundreise fragen. Dann kann zwar anhand einer gegebenen Lösung mit einer DTM in Polynomialzeit überprüft werden, ob es sich wirklich um eine Rundreise handelt, nicht aber, ob der gefundene Weg auch wirklich der kürzeste ist. Folglich liegt dieses Optimierungsproblem nicht in NP und ist nicht NP-vollständig.

 

[abc66]

Und was gilt nun für das Finden eines Unifikators mit n Variablen?

 

[httpdigest]

Und was gilt nun für das Finden eines Unifikators mit n Variablen?

Hat doch mit dem ursprünglichen Problem dieses Threads gar nichts zu tun.

Wenn man das Problem wirklich mit einer Sequenz aus replace/replaceAll Aufrufen lösen möchte, muss man nur die ungeordnete Menge an Ersetzungen (a -> b) in eine Ordnung bringen, so dass eine Ersetzung (a -> b) immer strikt nach (b -> c) kommt. Das erreicht man durch einfaches Sortieren:

import java.util.*;
public class RichtigErsetzen {
  public static String ersetzeRichtig(String str, Map<Character, Character> replacements) {
    return replacements.entrySet().stream()
        .sorted((a, b) -> a.getKey().equals(b.getValue()) ? -1 :
                          b.getKey().equals(a.getValue()) ? +1 :
                          0)
        .reduce(str, (s, e) -> s.replace(e.getKey(), e.getValue()), (a, b) -> a + b);
  }
  public static void main(String[] args) {
    System.out.println(ersetzeRichtig("abcdefg", map(
      'a', 'b',
      'b', 'c',
      'c', 'd',
      'd', 'e'
    )));
  }

  // Hilfsmethode, um eine Map mittels varargs zu erzeugen
  private static Map<Character, Character> map(Character... keyAndValue) {
    Map<Character, Character> m = new HashMap<Character, Character>();
    for (int i = 0; i < keyAndValue.length; i += 2)
      m.put(keyAndValue[i], keyAndValue[i+1]);
    return m;
  }
}

Voraussetzungen ist das Nichtvorhandensein von Zyklen wie von @LimDul genannt.

 

[httpdigest]

Wieso "und nicht schneller"?!?

Ups, ich meinte "und nicht langsamer"

 

[mihe7]

Und was gilt nun für das Finden eines Unifikators mit n Variablen?

Meinst Du https://de.wikipedia.org/wiki/Unifikation_(Logik)#Unifikationsalgorithmus ?

 

[abc66]

Hat doch mit dem ursprünglichen Problem dieses Threads gar nichts zu tun

natürlich, weil danach gefragt wurde

das Problem wirklich mit einer Sequenz aus replace/replaceAll Aufrufen lösen möchte

Das erreicht man durch einfaches Sortieren

leider hast recht.

Btw. es ist etwas blöd gelöst, aber der combiner bei reduce() übernimmt keine Funktion, er muss aber dennoch instantiiert werden:

	public static String ersetzeRichtig(String str, Map<Character, Character> replacements) {
		return replacements.entrySet().stream()
	        .sorted((a, b) -> a.getKey().equals(b.getValue()) ? -1 :
	                          b.getKey().equals(a.getValue()) ? +1 :
	                          0)
	        .reduce(str, (s, e) -> s.replace(e.getKey(), e.getValue()), (a,b)->null);
	}

 

[abc66]

Meinst Du https://de.wikipedia.org/wiki/Unifikation_(Logik)#Unifikationsalgorithmus ?

ehm, ja

 

[Miene1289]

Vielen Dank für eure Überlegungen. Ich werde mich mal ausprobieren. Vielleicht geht's ja auch mit dem ganzen Alphabet.

 

[abc66]

Vielleicht geht's ja auch mit dem ganzen Alphabet.

Da diese Menge ein Ring wäre, gäbe es unweigerlich Zyklen - also würde das nicht klappen - es sei denn, Du ersetzt wie schon oft angemerkt wurde Zeichen für Zeichen.

@httpdigest Ist Sortieren die "optimalste" Lösung für dieses Problem?

 

[httpdigest]

@httpdigest Ist Sortieren die "optimalste" Lösung für dieses Problem?

Ich denke schon, ja.
Es ist eine O(m*n*log(n) + n*log(n)) = O(m*n*log(n)) Lösung (mit m = Länge des Strings, in welchem die Ersetzungen vorgenommen werden sollen; n = Anzahl der Ersetzungen), da wir `n` Mal über den ganzen String der Länge `m` rennen müssen, um alle `n` Ersetzungen vorzunehmen (in der Annahme, dass String.replace() eine O(m) Operation ist, mit m = Länge des Strings). Dazu müssen wir noch einmal die Ersetzungen mit O(n * log(n)) sortieren. Ich wüsste nicht, wie das noch schneller gehen können soll. Irgendeine Art einer "Sortierung" (bzw. eine n*log(n)) Operation braucht man hier garantiert. Einfach nur einmal über alle Ersetzungen zu rennen und eine konstante Operation auszuführen, also O(n), reicht hier ziemlich sicher nicht, da eine Ersetzung ja eventuell von einer anderen Ersetzung in der Anwendungsreihenfolge abhängt und diese erstmal gefunden werden muss. Also schneller als O(n*log(n)) wird das nicht gehen.
Die bei weitem beste Variante wäre, wie ja schon so oft erwähnt, zeichenweise zu ersetzen, mit dann im Optimalfall O(m * log(n)), also über jedes Zeichen des `m` Zeichen langen Strings rennen und per O(log(n)) die Ersetzung für dieses Zeichen suchen.

 

[mihe7]

da eine Ersetzung ja eventuell von einer anderen Ersetzung in der Anwendungsreihenfolge abhängt und diese erstmal gefunden werden muss.

Müsste dann hier

    System.out.println(ersetzeRichtig("abcdefg", map(
      'a', 'b',
      'b', 'c',
      'c', 'd',
      'd', 'e'
    )));

nicht alles einfach durch ein e ersetzt werden (a->b->c->...->e) oder sehe ich was falsch?

 

[httpdigest]

Naja, nein. Die Idee war ja, zu sagen: Ersetze jedes "a" im Originalstring durch ein "b" und ersetze jedes "b" im Originalstring durch ein "c" und ersetze jedes "c" im Originalstring durch ein "d", usw. Und genau das macht der Code.
Bzw. war ja genau das Problem des Fragestellers, dass bei wiederholter Ersetzung mit replace() auf den bereits ersetzten Teilergebnissen vorheriger Ersetzungen das Gesamtergebnis dann falsch ist, weil Ersetzungen frühere Ersetzung ersetzen.

 

[mihe7]

Naja, nein. Die Idee war ja, zu sagen: Ersetze jedes "a" im Originalstring durch ein "b" und ersetze jedes "b" im Originalstring durch ein "c" und ersetze jedes "c" im Originalstring durch ein "d", usw. Und genau das macht der Code.

So hatte ich den Code auch verstanden, aber hier habe ich ein Problem:

Einfach nur einmal über alle Ersetzungen zu rennen und eine konstante Operation auszuführen, also O(n), reicht hier ziemlich sicher nicht, da eine Ersetzung ja eventuell von einer anderen Ersetzung in der Anwendungsreihenfolge abhängt und diese erstmal gefunden werden muss.

für jedes Zeichen in String s
    ersetze Zeichen durch Entsprechung aus Map (O(1))

Macht O(n)

 

[httpdigest]

Aber das Suchen in der Map ist nicht O(1). Und ich nehme mal an, dass dein `n` hier die Anzahl der Zeichen im String ist und nicht die Anzahl der Ersetzungen?

 

[httpdigest]

Ach so, naja gut, wenn wir eine HashMap nehmen und mal von O(1) Suche ausgehen, dann ist die optimale Lösung mit Ersetzen jedes Zeichens separat O(m) (mit m = Anzahl der Zeichen im String).
Sowas in der Art meinte ich auch in dem letzten Satz:

Die bei weitem beste Variante wäre, wie ja schon so oft erwähnt, zeichenweise zu ersetzen, mit dann im Optimalfall O(m * log(n)), also über jedes Zeichen des `m` Zeichen langen Strings rennen und per O(log(n)) die Ersetzung für dieses Zeichen suchen.

Und ich nahm naiverweise an, dass Suchen = O(log(n)), aber für HashMaps ist es im besten Fall ja O(1), also ja: O(m).

 

[mihe7]

Hm... bei mir steht in der HashMap: This implementation provides constant-time performance for the basic operations (get and put), auch wäre ein char-Array als Map möglich:

public class Test {
    static char[] map = new char[256];
    static {
        for (int i = 0;i < map.length; i++) { map[i] = (char)i; }
        map['a']='b';
        map['b']='c';
        map['c']='d';
        map['d']='e';
    }

    static String encode(String s) {
        StringBuilder b = new StringBuilder();
        for (char ch : s.toCharArray()) {
            b.append(map[ch]);
        }
        return b.toString();
    }

    public static void main(String[] args) {
        System.out.println(encode("abcdefg"));
    }
}

EDIT: Post ist hinfällig, habe gerade gesehen, dass @httpdigest schon alles aufgeklärt hat.