隣接文字のない文字列のすべての順列を生成するアルゴリズム

Question

私はABCDEFを持っているとしましょう。その後、6があります！その文字列を並び替える順列。さて、私は、隣接する文字がない順列についてのみ扱いたいと思います。ことは、私これらの制約を満たすすべての順列を見てみたい：

• BはAの隣にないか、またはC
• CはBの隣ではないか、D
• DはCの隣ではありません

  //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 
  

  ：またはE
• Eは、このアルゴリズムへの私のアプローチは、以下の擬似コードであるDまたはF

の隣ではありません3210

しかし、これらのマスキング操作は非常に非効率的になり、特に私の文字列の長さが6より大きい場合、私は非常に長くなりすぎます。これをより効率的に行うにはどうすればいいですか？私はこれらの類似の投稿、1,2を見て、私を助けるかもしれないいくつかの重要なアイデアを抽出したいと考えていました。しかし、これはブルートフォースチェックでもあります。私は実際に最初からユニークなパターンだけを生成し、すべてを生成して1つずつチェックする必要はありません。

EDIT：現在のところ、これは私がすべての順列を生成するために使用しているものです。

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

ここでは、並べ替えに隣接する文字を追加する前に検索をプルーニングする、かなり簡単なバックトラックソリューションがあります。

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); 
     } 
    } 

} 

これは、ABCDEFの90の順列を出力します。私はちょうど始めと終わりを引用するでしょう：

Answer 2

アルゴリズムの典型的O(n!)擬似コード長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 
     } 
    } 
} 

ストリングABCに対応する再帰ツリーは、[インターネットから撮影した画像]のように見える：

交換する直前に、与えられた制約を満足するよう交換することができます（s[left]とs[i]の新しい前後の次の文字をチェックします）。これにより、再帰ツリーの多くの分岐も切り捨てられます。