排座位要安排：3个A国人，3个B国人，3个C国人坐成一排。要求不能使连续的3个人是同一个国籍。求所有不同方案的总数？

小灰灰 2022-06-06 00:15 135阅读 0赞

/* 排座位 要安排：3个A国人，3个B国人，3个C国人坐成一排。 要求不能使连续的3个人是同一个国籍。 求所有不同方案的总数？ */
    public class T13 {
        static int sum = 0; // 不同方案总个数
        // 检查是否有同一国人连续3个
        public static boolean check(char[] c){
            int count = 1;  // 初始个数
            for(int i=0;i<c.length-1;i++){
                if(c[i]==c[i+1]){
                    count++;
                }else{
                    count = 1;  // 初始个数
                }
                if(count>=3) return true;
            }
            return false;
        }
        // 全排列
        public static void allSort(char[] c,int start,int end){
            if(start>end){
                if(!check(c)){  // 检查是否有同一国人连续3个
                    sum++;      // 不同方案总个数加1
                }
                return ;
            }else{
                for(int i=start;i<=end;i++){
                    char temp = c[i];
                    c[i] = c[start];
                    c[start] = temp;
                    allSort(c,start+1,end); // 递归
                    temp = c[i];
                    c[i] = c[start];
                    c[start] = temp;
                }
            }
        }
        public static void main(String[] args){
            char[] c = {
       'A','A','A','B','B','B','C','C','C'};
            allSort(c,0,c.length-1);    // 全排列
            System.out.println(sum);
        }
    }

转载自：

> [http://blog.csdn.net/hanshileiai/article/details/8825750][http_blog.csdn.net_hanshileiai_article_details_8825750]

[http_blog.csdn.net_hanshileiai_article_details_8825750]: http://blog.csdn.net/hanshileiai/article/details/8825750