Algorithmus zum Generieren aller Permutationen einer Zeichenfolge ohne benachbarte Zeichen

Question

Sagen wir, ich habe ABCDEF. Dann sind es 6! Permutationen der Neuordnung dieser Zeichenfolge. Nun möchte ich nur auf die Permutationen eingehen, in denen es keine benachbarten Zeichen gibt. Das heißt, ich will an allen Permutationen suchen, die diese Bedingungen erfüllen:

• B ist nicht neben A oder C
• C nicht weiter nach B oder D
• D ist nicht neben C oder E
• E nicht neben D oder F

diesen Algorithmus Mein Ansatz ist der folgende Pseudo-Code:

//generate all 6! permutations 
//check all permutations and see where B is next to A || C 
    //remove all instances 
//check all permutations and see where C is next to D 
    //remove all instances 
//check all permutations and see where D is next to E 
    //remove all instances 
//check all permutations and see where E is next to F 
    //remove all instances 

Diese Maskierungsoperationen werden jedoch sehr ineffizient und dauern viel zu lange, besonders wenn meine Stringlänge größer als 6 ist. Wie kann ich das effizienter machen? Ich sehe diese ähnlichen Beiträge, 1, 2, und hoffte, einige Schlüsselideen zu extrahieren, die mir helfen könnten. Dies ist jedoch auch eine Brute-Force-Prüfung. Ich möchte eigentlich nur die einzigartigen Muster von Anfang an generieren und nicht alles erzeugen und eins nach dem anderen überprüfen.

EDIT: Derzeit ist das, was ich benutze, um alle Permutationen zu generieren.

static String[] designs; 
static int index; 
protected static String[] generateDesigns(int lengthOfSequence, int numOfPermutations){ 
    designs = new String[numOfPermutations]; 
    StringBuilder str = new StringBuilder("1"); 
    for(int i = 2; i <= lengthOfSequence; i++) 
     str.append(i); 

    genDesigns("", str.toString()); //genDesigns(6) = 123456 will be the unique characters 
    return designs; 
} 

//generate all permutations for lenOfSequence characters 
protected static void genDesigns(String prefix, String data){ 
    int n = data.length(); 
    if (n == 0) designs[index++] = prefix; 
    else { 
     for (int i = 0; i < n; i++) 
      genDesigns(prefix + data.charAt(i), data.substring(0, i) + data.substring(i+1, n)); 
    } 
} 

Answer 1

Hier ist eine relativ einfache Backtracking-Lösung, die die Suche vor dem Hinzufügen eines benachbarten Zeichens zur Permutation einschränkt.

public class PermutationsNoAdjacent { 

    private char[] inputChars; 
    private boolean[] inputUsed; 
    private char[] outputChars; 
    private List<String> permutations = new ArrayList<>(); 

    public PermutationsNoAdjacent(String inputString) { 
     inputChars = inputString.toCharArray(); 
     inputUsed = new boolean[inputString.length()]; 
     outputChars = new char[inputString.length()]; 
    } 

    private String[] generatePermutations() { 
     tryFirst(); 
     return permutations.toArray(new String[permutations.size()]); 
    } 

    private void tryFirst() { 
     for (int inputIndex = 0; inputIndex < inputChars.length; inputIndex++) { 
      assert !inputUsed[inputIndex] : inputIndex; 
      outputChars[0] = inputChars[inputIndex]; 
      inputUsed[inputIndex] = true; 
      tryNext(inputIndex, 1); 
      inputUsed[inputIndex] = false; 
     } 
    } 

    private void tryNext(int previousInputIndex, int outputIndex) { 
     if (outputIndex == outputChars.length) { // done 
      permutations.add(new String(outputChars)); 
     } else { 
      // avoid previousInputIndex and adjecent indices 
      for (int inputIndex = 0; inputIndex < previousInputIndex - 1; inputIndex++) { 
       if (!inputUsed[inputIndex]) { 
        outputChars[outputIndex] = inputChars[inputIndex]; 
        inputUsed[inputIndex] = true; 
        tryNext(inputIndex, outputIndex + 1); 
        inputUsed[inputIndex] = false; 
       } 
      } 
      for (int inputIndex = previousInputIndex + 2; inputIndex < inputChars.length; inputIndex++) { 
       if (!inputUsed[inputIndex]) { 
        outputChars[outputIndex] = inputChars[inputIndex]; 
        inputUsed[inputIndex] = true; 
        tryNext(inputIndex, outputIndex + 1); 
        inputUsed[inputIndex] = false; 
       } 
      } 
     } 
    } 

    public static void main(String... args) { 
     String[] permutations = new PermutationsNoAdjacent("ABCDEF").generatePermutations(); 
     for (String permutation : permutations) { 
      System.out.println(permutation); 
     } 
    } 

} 

Es druckt 90 Permutationen von ABCDEF. Ich gebe nur den Anfang und das Ende an:

ACEBDF 
ACEBFD 
ACFDBE 
ADBECF 
… 
FDBEAC 
FDBECA 

Answer 2

Der typische O(n!) Pseudo-Code des Algorithmus alle Permutationen einer Zeichenkette von Länge zu erzeugen n:

function permute(String s, int left, int right) 
{ 
    if (left == right) 
    print s 
    else 
    { 
     for (int i = left; i <= right; i++) 
     { 
      swap(s[left], s[i]); 
      permute(s, left + 1, right); 
      swap(s[left], s[i]); // backtrack 
     } 
    } 
} 

Die entsprechende Rekursionsbaum für String ABC sieht aus wie [Bild aus dem Internet genommen]:

Kurz vor dem Austausch prüfen, ob yo Sie können die gegebene Einschränkung umgehen (Überprüfung der neuen vorherigen und neuen nächsten Zeichen von s[left] und s[i]). Dadurch werden auch viele Zweige vom Rekursionsbaum abgeschnitten.