上次碰到一个面试  题目好像是这样的
题目：用1、2、2、3、4、5这六个数字，用C写一个main函数，打印出所有不同的排列，如：512234、412345等，要求：”4″不能在第三位，”3″与”5″不能相连.我没写出..希望大家帮我看一下 到底怎么该怎么写？

求助..ing

写了一个，不知道对不对。

#include <stdio.h>

static int path[6];
static int data[6]={1,2,2,3,4,5};
int count;
bool IsSafe(int pos,int index)       
{
    if( pos == 2 && data[index] == 4)
        return false;
    if(pos > 0 && path[pos-1] == 3 && data[index] == 5)
        return false;
    if(pos > 0 && path[pos-1] == 5 && data[index] == 3)
        return false;
    for( int i = 0; i < pos; i++)
        if( path[i] == index)
            return false;
    return true;
}

void print()
{
    count++;
    for( int i = 0; i != 6; ++i)
        printf("%d",data[path[i]]);
    printf("\t");
}
void trial(int pos)
{
    if (pos >= 6)
        print();
    else for(int i=0; i<6;i++)
            {
               
                if(IsSafe(pos,i))
                {
                    path[pos]=i;
                    trial(pos+1);
                }
            }
}

int main()
{
    trial(0);
    printf("\ntotal counts:%d\n",count);
    return 0;
}

void swap(char* a, char* b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void permutate(char* str, int begin, int end)
{
    if(begin == end)
    {
        int isOutput = 0;
        for (int i=0; i<strlen(str); i++)
        {
            if (str[2]!=4)
            {
                if (i!=(strlen(str)-1))
                {
                    if ((str[i]+str[i+1])!=8)
                    {
                        isOutput = 1;                    
                    }
                }
                else
                {
                    if ((str[i]+str[i-1])!=8)
                    {
                        isOutput = 1;
                    }
                }
            }
        }
        printf("%s\n",str);
    }
    else
    {
        for(int i=begin; i<end; i++)
        {
            swap(str+begin,str+i);
            permutate(str, begin+1, end);
            swap(str+begin,str+i);
        }
    }
}

int main (int argc, const char * argv[]) {
    char str[] = "122345";
    int len = strlen(str);
    permutate(str, 0, len);
    return 0;
}
直接复制过去，运行吧

LS的输出来就是全排呀
我的有一个小问题，不过貌似对结果也没影响。

呵呵，忘掉了一句话，现在就ok了
void swap(char* a, char* b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void permutate(char* str, int begin, int end)
{
    if(begin == end)
    {
        int isOutput = 0;
        for (int i=0; i<strlen(str); i++)
        {
            if (str[2]!=4)
            {
                if (i!=(strlen(str)-1))
                {
                    if ((str[i]+str[i+1])!=8)
                    {
                        isOutput = 1;                    
                    }
                }
                else
                {
                    if ((str[i]+str[i-1])!=8)
                    {
                        isOutput = 1;
                    }
                }
            }
        }
        if (isOutput==1)
            printf("%s\n",str);
    }
    else
    {
        for(int i=begin; i<end; i++)
        {
            swap(str+begin,str+i);
            permutate(str, begin+1, end);
            swap(str+begin,str+i);
        }
    }
}

int main (int argc, const char * argv[]) {
    char str[] = "122345";
    int len = strlen(str);
    permutate(str, 0, len);
    return 0;
}

话说我早就看到这个isOutput了。
不过加了也还是全排的。

这个一定可以满足你  我已经在北航OJ上测试过了  输入5就可以

你的条件不涉及到6

#include<stdio.h>
void dfs(bool foot[],int mem[],int depth,int n)
{
    int i;
    if(n == depth)
    {       
        for(i = 0;i<n-1;i++)
            printf("%d ",mem[i]);
        printf("%d\n",mem[i]);
        return ;
    }
    for(i = 0;i<n;i++)
    {
        if(!foot[i])
        {
            if(4 == i+1 && 2 == depth ||
                mem[depth-1] == 3 && 5 == i+1 ||
                mem[depth-1] == 5 && 3 == i+1)
                continue;
            foot[i] = true;
            mem[depth] = i+1;
            dfs(foot,mem,depth+1,n);
            foot[i] = false;
        }
    }
}
int main()
{
    int i,j,n;
    scanf("%d",&n);
    while(n--)
    {
        bool foot[8] = {0};
        int mem[8] = {0};
        int s;
        scanf("%d",&s);
        dfs(foot,mem,0,s);
    }
    return 0;
}

谢谢大家...

这次绝对不是全排了
void swap(char* a, char* b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void permutate(char* str, int begin, int end)
{
    if(begin == end)
    {
        int isOutput = 0;
        for (int i=0; i<strlen(str); i++)
        {
            if (str[2]!='4')
            {
                if (i!=(strlen(str)-1))
                {
                    if (((int)str[i]+(int)str[i+1])!=104)
                    {
                        isOutput = 1;   
                    }
                    else
                    {
                        isOutput = 0;
                        break;
                    }

                }
                else
                {
                    if (((int)str[i]+(int)str[i+1])!=104)
                    {
                        isOutput = 1;
                    }
                    else
                    {
                        isOutput = 0;
                        break;
                    }
                }
            }
            else {
                isOutput = 0;
                break;
            }

        }
        if (isOutput) {
            printf("%s\n",str);
            
        }
    }
    else
    {
        for(int i=begin; i<end; i++)
        {
            swap(str+begin,str+i);
            permutate(str, begin+1, end);
            swap(str+begin,str+i);
        }
    }
}

int main (int argc, const char * argv[]) {
    char str[] = "122345";
    int len = strlen(str);
    permutate(str, 0, len);
    return 0;
}