生成没有相邻字符的字符串的所有排列的算法

Question

让我说我有ABCDEF.然后,有6个!重新排序该字符串的排列.现在,我只想处理没有相邻字符的排列.这意味着,我想看看满足这些约束的所有排列:

• B不在A或C旁边
• C不在B或D旁边
• D不在C或E旁边
• E不在D或F旁边

我对此算法的处理方法是以下伪代码:

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

然而,这些掩蔽操作变得非常低效并且花费我太长时间,特别是如果我的字符串长度大于6.我怎样才能更有效地做到这一点？我看到这些类似的帖子,1,2,并希望提取一些关键概念,可以帮助我.但是,这也是强力检查.我想从一开始就只生成独特的模式,而不必生成所有内容并逐个检查.

编辑:目前这是我用来生成所有排列的东西.

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

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]).这也会减少递归树的许多分支.