Verschlüsselung mit replace()

M

Miene1289

Mitglied
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.
 
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.
 
Hier bitte
Java: 
	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);
	}
 
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 hat gesagt.:
das ist NP-vollständig...
Zum Vergrößern anklicken....
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.
 
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.
 
httpdigest hat gesagt.:
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.
Zum Vergrößern anklicken....
Den angegebenen, "naiven" Algorithmus habe ich in 10 Minuten geschrieben - durchaus möglich, das er nicht perfekt ist.
 
abc66 hat gesagt.:
Den angegebenen, "naiven" Algorithmus habe ich in 10 Minuten geschrieben - durchaus möglich, das er nicht perfekt ist.
Zum Vergrößern anklicken....
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:
Java: 
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'
    )));
  }
}
 
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?
 
abc66 hat gesagt.:
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.
Zum Vergrößern anklicken....
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.
abc66 hat gesagt.:
2^n zählt doch zum Beispiel dazu?
Zum Vergrößern anklicken....
Welches Beispiel meinst du, und was meinst du mit "dazuzählen"?
 
abc66 hat gesagt.:
Nach meiner Meinung, sucht er einfach eine Reihenfolge der Ersetzungen, mit der er replaceAll(...,ersetzung_i); aufrufen kann.
Zum Vergrößern anklicken....
Ähm, nö. Sie oder er möchte einfach ihr oder sein Problem lösen und replace() war nur ein Versuch ihrerseits oder seinerseits:
Miene1289 hat gesagt.:
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?
Zum Vergrößern anklicken....
Insofern ist der Ansatz von @LimDul nicht schlecht.
 
temi hat gesagt.:
Ähm, nö. Sie oder er möchte einfach ihr oder sein Problem lösen und replace() war nur ein Versuch ihrerseits oder seinerseits
Zum Vergrößern anklicken....
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.
 
abc66 hat gesagt.:
O(2^n) polynomielles Wachstum und ein (nur) in dieser Zeit lösbares Problem wäre np-vollständig, oder nicht?
Zum Vergrößern anklicken....
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
 
Zuletzt bearbeitet:
httpdigest hat gesagt.:
Jetzt muss die Prüfung, ob dies auch eine gültige Lösung des Problems ist, in deterministisch polynomieller Zeit erfolgen (und nicht schneller).
Zum Vergrößern anklicken....
Wieso "und nicht schneller"?!?

abc66 hat gesagt.:
Die Prüfung einer Lösung, ob sie gültig ist, erfolgt bei mir aber in n...
Zum Vergrößern anklicken....
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 hat gesagt.:
Und was gilt nun für das Finden eines Unifikators mit n Variablen?
Zum Vergrößern anklicken....
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:
Java: 
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.
 
Zuletzt bearbeitet:
httpdigest hat gesagt.:
Hat doch mit dem ursprünglichen Problem dieses Threads gar nichts zu tun
Zum Vergrößern anklicken....
natürlich, weil danach gefragt wurde
httpdigest hat gesagt.:
das Problem wirklich mit einer Sequenz aus replace/replaceAll Aufrufen lösen möchte
Zum Vergrößern anklicken....
httpdigest hat gesagt.:
Das erreicht man durch einfaches Sortieren
Zum Vergrößern anklicken....
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:
Java: 
	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 hat gesagt.:
@httpdigest Ist Sortieren die "optimalste" Lösung für dieses Problem?
Zum Vergrößern anklicken....
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.
 
httpdigest hat gesagt.:
da eine Ersetzung ja eventuell von einer anderen Ersetzung in der Anwendungsreihenfolge abhängt und diese erstmal gefunden werden muss.
Zum Vergrößern anklicken....
Müsste dann hier
Java: 
    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?
 
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. 🙂
 
httpdigest hat gesagt.:
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.
Zum Vergrößern anklicken....
So hatte ich den Code auch verstanden, aber hier habe ich ein Problem:

httpdigest hat gesagt.:
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.
Zum Vergrößern anklicken....

Code: 
für jedes Zeichen in String s
    ersetze Zeichen durch Entsprechung aus Map (O(1))
Macht O(n) 🙂
 
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?
 
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:
httpdigest hat gesagt.:
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.
Zum Vergrößern anklicken....
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).
 
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:
Java: 
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.
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Probleme mit der String Methode replace()
Antworten: 4
String mit replace bearbeiten
Antworten: 2
Abstruse Probleme mit eigenem replace Algorithmus
Antworten: 11
Regulärer Ausruck mit replace
Antworten: 3
String filtern mit replace -> Problem
Antworten: 6

Zurück
Oben