紧急求助：关于求全排列算法的问题

算法要求：
在26个字母里面任选7个不同的字母，求这7个字母的全排列，要求3个以上相邻字母(如abc)不能排在一起。

7 个解决方案

#1

组合数学里有专门的求全排列的算法
稍稍改改就可以了

#2

第一步,取随机数产生字母,可以采用许多算法,添加到一个数组中并排序,
第二步,产生全排列并排除不符合要求的数据,这里排除时可以适当采用一些算法减少时间度.

#3

1、用递归算法得出所有的排列；
2、在1的结果中排除有3个相邻字母的。

BTW: 要排列的字母是通过键盘输入的，而不是程序随机产生。
     鉴于7个字母的排列数太多(4547个)，可以用4、5个字母的测试一下。
     我在BCC5.5下编译并运行，没有问题。
----------------------------------------------
#include <iostream>
#include <string>
#include <list>
using namespace std;

string slist="";
string sresult="";
int listlen=0;
int ex=0;

string permute(string list) {
  string strreturn="";
  int ln=list.length();

  if( ln==2 ) {
    strreturn=list;

    char temp;
    temp=list[0];
    list[0]=list[1];
    list[1]=temp;

    return strreturn+list;
  }

  string substr="";
  string strtemp="";
  for(int i=0; i<ln; ++i) {
    strtemp.clear();
    substr.clear();

    if( i>0 )  substr += list.substr(0,i);
    if( i<ln-1 ) substr += list.substr(i+1, ln-1);

    int lntemp=ln-1;
    long FN=lntemp;
    while( --lntemp!=1 ) FN*=lntemp;

    lntemp=ln-1;
    string str=permute(substr);
    for(int j=0; j<FN; ++j) {
      strtemp += list[i]+str.substr(j*lntemp, lntemp);
    }

    strreturn += strtemp;
  }
  return strreturn;
}

int main() {
  cout<<"Enter the characters to permute: ";
  getline(cin, slist);

  listlen = slist.length()-1;

  slist = slist.substr(0, listlen);
  sresult=permute(slist);

  int lntemp=listlen;
  long FN=lntemp;
  while( --lntemp!=1 ) FN*=lntemp;

//排除有3个连续字母的...
  string str="";
  lntemp=listlen;
  for(int i=0; i<FN; ++i) {
    str=sresult.substr(i*lntemp, lntemp);
    for( int j=0; j<lntemp-2; ++j ) {
       if( str[j]==str[j+1]-1 && str[j+1]==str[j+2]-1 ) {
         sresult.erase( i*lntemp, lntemp ); //删除之
         --i;
         --FN;
         cout<<str<<"...";           //显示被排除的排列
         break;
       }
    }
  }

cout<<endl;
  for(int i=0; i<FN; ++i) {
    str=sresult.substr(i*lntemp, lntemp);
    cout<<str<<"...";
  }
  cout<<FN<<endl;           //符合要求的排列数
}

#4

这是我见过和用过的最快的算法.
今天没有时间了.明天再说吧

#5

算移位法求排列吧

#6

这是一个纯粹的数学问题，
先求7个字母的全排列，然后减去7个字符中有至少三个相邻字符排在一起的情况。

#7

使用C++
使用C++
template<typename Type>
void swap(Type &a, Type &b )
{
Type c;
c = a;
a = b;
b = c;
}

void Arrange( char * source ,int num )
{
if( num == 1 )
return;
int i,j;
for( i = 0; i< num ; i ++ )
{
for( j = i ; j < num ; j++ )
{
swap( source[i] , source[j] );
Arrange( source+1, num-1);
swap( source[i], source[j] );
}
}
}

#1