【230913-2】将1，2，3，4，5，6，7排成先减后增的序列，共有几种排法？

【数学思路】

初看这个问题，似乎抓不到头绪，但抓住1这个关键点后，问题便迎刃而解了。

1这个数，在排列好的序列中，必然处于波谷位置，其左边的数呈递减趋势，右边的数呈递增趋势，都比1大。

既然是波谷，1就不可能处于序列的首位或末位，只能在中间。

至此，问题就变成了：从2，3，4，5，6，7中选择若干数排到1的左右两侧，形成先减后增的序列，共有几种排法？

如果1在第二位，就有C_6_1种选法，1左右两边的数排序后只有一种方式，不需要再深入讨论；

如果1在第二位，就有C_6_2种选法；

....

如果1在第六位，就有C_6_5种选法；

总计：Sum=C_6_1+C_6_2+C_6_3+C_6_4+C_6_5=2*C_6_1+2*C_6_2+C_6_3=2*6+(2*6*5/2/1)+6*5*4/3/2/1=12+2*15+20=62种拍法。

学好数学如果只是基础扎实，没有盲区，计算失误率低，那只能在高考中获得百分之八十左右的分数；如果想要更高，缺乏巧智是做不到的。

上题中的1就是关键的巧智，是需要在刷题中着重培养的能力。换个方式，如果需要先增后减的序列，那么7就在波峰的位置，思路和本题是一样的。

有这种巧智的同学，理当进入大国的航空航天部门，才能一展所长。如果进入外企或是一般国企，看到当年高考中被数学虐得死去活来的二传手翻译官们和上面有人的拿摩温们拿着居然比自己高的薪水，智商与薪水倒挂，胸中波澜岂能平息？

【程序思路一】

如果想验证数学思路的正确性，可以做一个七位数的全排列器，在筛选时先找到1的位置，然后看1左边的数是否递减，1右边的数是否递增，然后输出符合条件的排列方式。

辅助类Arranger：

package test230913;

import java.util.ArrayList;
import java.util.List;

/**
 * 用于产生排列结果的工具类
 * 从n个元素中取出m个元素，按照一定的顺序排成一列。得到所有排列的方案
 */
class Arranger {
    // 保存在内部的对原始元素数组的引用
    private int[] arr;

    // 总计多少元素，此即数组长度
    private final int n;

    // 选多少个
    private final int m;

    // 返回结果
    private List<List<Integer>> results;

    /**
     * 构造函数一
     * 这个构造函数是用于全排列的（n=m=数组长度）
     *
     * @arr 原始元素数组
     */
    public Arranger(int[] arr) {
        this.arr = arr;
        this.n = arr.length;
        this.m = arr.length;

        this.results = new ArrayList<>();
        doArrange(new ArrayList<>());
    }

    /**
     * 构造函数二
     * 这个构造函数是用于部分排列的(m<n=数组长度)
     *
     * @param arr    原始元素数组
     * @param selCnt 选多少个
     */
    public Arranger(int[] arr, int selCnt) {
        this.arr = arr;
        this.n = arr.length;
        this.m = selCnt;
        if (m > n) {
            throw new ArrayIndexOutOfBoundsException("m:" + m + " >n:" + n);
        }

        this.results = new ArrayList<>();
        doArrange(new ArrayList<>());
    }

    /**
     * 使用递归进行全排列，结果放在results中
     *
     * @param initialList 初始链表
     */
    private void doArrange(List<Integer> initialList) {
        List<Integer> innerList = new ArrayList<>(initialList);

        if (m == initialList.size()) {
            results.add(innerList);
        }

        for (int i = 0; i < arr.length; i++) {
            if (innerList.contains(arr[i])) {
                continue;
            }

            innerList.add(arr[i]);
            doArrange(innerList);
            innerList.remove(innerList.size() - 1);
        }
    }

    /**
     * 获得结果链表的引用
     *
     * @return
     */
    public List<List<Integer>> getResults() {
        return results;
    }

    // 测试
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4};
        Arranger arranger = new Arranger(numbers);

        System.out.println("四元素全排列示例:");
        int idx = 0;
        for (List<Integer> re : arranger.getResults()) {
            System.out.println(String.format("%02d", ++idx) + "." + re);
        }

        Arranger arranger2 = new Arranger(numbers, 2);
        System.out.println("\n四选二排列示例:");
        idx = 0;
        for (List<Integer> re : arranger2.getResults()) {
            System.out.println(String.format("%02d", ++idx) + "." + re);
        }
    }
}

主类Valley1：

package test230913;

import java.util.List;

/**
 * 
 * 将1，2，3，4，5，6，7排成先减后增的序列，共有几种排法
 * 排列后进行筛选
 * 
 */
public class Valley1 {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 6, 7};
        Arranger arranger = new Arranger(numbers);
        
        int idx = 0;
        for (List<Integer> results : arranger.getResults()) {
            int pos=-1;
            
            // 找到1的位置
            for(int i=0;i<results.size();i++) {
                if(1==results.get(i)) {
                    pos=i;
                    break;
                }
            }
            
            // 1只能在中间
            if(pos==0 || pos==results.size()-1) {
                continue;
            }
            
            // 保证1的左边是递减的
            boolean isDecrease=true;
            for(int i=0;i<pos-1;i++) {
                if(results.get(i)<results.get(i+1)) {
                    isDecrease=false;
                    break;
                }
            }
            if(!isDecrease) {
                continue;
            }
            
            // 保证1的右边是递增的
            boolean isIncrease=true;
            for(int i=pos;i<results.size()-1;i++) {
                if(results.get(i)>results.get(i+1)) {
                    isIncrease=false;
                    break;
                }
            }
            if(!isIncrease) {
                continue;
            }
            
            // 最终输出符合条件的序列
            System.out.println(String.format("%02d", ++idx) + "." + results);
        }
    }
}

输出：

01.[2, 1, 3, 4, 5, 6, 7]
02.[3, 1, 2, 4, 5, 6, 7]
03.[3, 2, 1, 4, 5, 6, 7]
04.[4, 1, 2, 3, 5, 6, 7]
05.[4, 2, 1, 3, 5, 6, 7]
06.[4, 3, 1, 2, 5, 6, 7]
07.[4, 3, 2, 1, 5, 6, 7]
08.[5, 1, 2, 3, 4, 6, 7]
09.[5, 2, 1, 3, 4, 6, 7]
10.[5, 3, 1, 2, 4, 6, 7]
11.[5, 3, 2, 1, 4, 6, 7]
12.[5, 4, 1, 2, 3, 6, 7]
13.[5, 4, 2, 1, 3, 6, 7]
14.[5, 4, 3, 1, 2, 6, 7]
15.[5, 4, 3, 2, 1, 6, 7]
16.[6, 1, 2, 3, 4, 5, 7]
17.[6, 2, 1, 3, 4, 5, 7]
18.[6, 3, 1, 2, 4, 5, 7]
19.[6, 3, 2, 1, 4, 5, 7]
20.[6, 4, 1, 2, 3, 5, 7]
21.[6, 4, 2, 1, 3, 5, 7]
22.[6, 4, 3, 1, 2, 5, 7]
23.[6, 4, 3, 2, 1, 5, 7]
24.[6, 5, 1, 2, 3, 4, 7]
25.[6, 5, 2, 1, 3, 4, 7]
26.[6, 5, 3, 1, 2, 4, 7]
27.[6, 5, 3, 2, 1, 4, 7]
28.[6, 5, 4, 1, 2, 3, 7]
29.[6, 5, 4, 2, 1, 3, 7]
30.[6, 5, 4, 3, 1, 2, 7]
31.[6, 5, 4, 3, 2, 1, 7]
32.[7, 1, 2, 3, 4, 5, 6]
33.[7, 2, 1, 3, 4, 5, 6]
34.[7, 3, 1, 2, 4, 5, 6]
35.[7, 3, 2, 1, 4, 5, 6]
36.[7, 4, 1, 2, 3, 5, 6]
37.[7, 4, 2, 1, 3, 5, 6]
38.[7, 4, 3, 1, 2, 5, 6]
39.[7, 4, 3, 2, 1, 5, 6]
40.[7, 5, 1, 2, 3, 4, 6]
41.[7, 5, 2, 1, 3, 4, 6]
42.[7, 5, 3, 1, 2, 4, 6]
43.[7, 5, 3, 2, 1, 4, 6]
44.[7, 5, 4, 1, 2, 3, 6]
45.[7, 5, 4, 2, 1, 3, 6]
46.[7, 5, 4, 3, 1, 2, 6]
47.[7, 5, 4, 3, 2, 1, 6]
48.[7, 6, 1, 2, 3, 4, 5]
49.[7, 6, 2, 1, 3, 4, 5]
50.[7, 6, 3, 1, 2, 4, 5]
51.[7, 6, 3, 2, 1, 4, 5]
52.[7, 6, 4, 1, 2, 3, 5]
53.[7, 6, 4, 2, 1, 3, 5]
54.[7, 6, 4, 3, 1, 2, 5]
55.[7, 6, 4, 3, 2, 1, 5]
56.[7, 6, 5, 1, 2, 3, 4]
57.[7, 6, 5, 2, 1, 3, 4]
58.[7, 6, 5, 3, 1, 2, 4]
59.[7, 6, 5, 3, 2, 1, 4]
60.[7, 6, 5, 4, 1, 2, 3]
61.[7, 6, 5, 4, 2, 1, 3]
62.[7, 6, 5, 4, 3, 1, 2]

结果与数学思路可以相互印证。

【程序思路二】

如果确认数学思路的正确性，但需要了解具体每一种排法，可以做一个6选n的选择器，n取1到5，选出的数逆序放到1的左边，剩下的数正序放到1的右边，然后输出。

辅助类Combination：

package test230913;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 数学中排列组合中的组合器实现
 * 传入一个数组及选择的个数，传出所有选择方案
 */
class Combination {
    /**
     * 用于存放中间结果
     */
    private Stack<Integer> stack;
    
    /**
     * 用于存放结果
     */
    private List<List<Integer>> results;
    
    /**
     * 构造函数
     * @param arr 进行组合的元素
     * @param count 选多少个
     */
    public Combination(int[] arr,int count) {
        if(count>arr.length) {
            throw new ArrayIndexOutOfBoundsException(count+">"+arr.length);
        }
        
        stack = new Stack<>();
        results=new ArrayList<>();
        doSelect(arr,count,0,0);
    }
    
    /**
     * 进行选择
     * @param arr 目标数组
     * @param expect 期望选择数量
     * @param actual 实际选择数量
     * @param current 当前下标
     */
    private void doSelect(int[] arr, int expect, int actual, int current) {
        if(actual == expect) {
            List<Integer> list=new ArrayList<>();
            
            for(int i:stack) {
                list.add(i);
            }
            
            results.add(list);
            
            return;
        }
         
        for(int i=current;i<arr.length;i++) {
            if(!stack.contains(arr[i])) {
                stack.add(arr[i]);
                doSelect(arr, expect, actual+1, i);
                stack.pop();
            }
        }
    }
    
    /**
     * 取得组合结果
     * @return
     */
    public List<List<Integer>> getResults(){
        return results;
    }
    
    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        final int[] arr= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30};
        final int count=2;
        
        Combination c=new Combination(arr,count);
        List<List<Integer>> results=c.getResults();
        
        int idx=0;
        for(List<Integer> res:results) {
            System.out.println(String.format("%02d", ++idx) +"."+res);
        }
    }
}

主类Valley2：

package test230913;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 将1，2，3，4，5，6，7排成先减后增的序列，共有几种排法
 * @author ufo
 *
 */
public class Valley2 {
    public static void main(String[] args) {
        final int[] arr= {2,3,4,5,6,7};
        
        int idx=0;
        for(int n=1;n<arr.length;n++) {
            Combination c=new Combination(arr,n);
            List<List<Integer>> results=c.getResults();
            
            for(List<Integer> result:results) {
                List<Integer> right=new ArrayList<>();
                
                for(int i:arr) {
                    if(isExist(i,result)==false) {
                        right.add(i);
                    }
                }
                
                Collections.sort(result);
                Collections.reverse(result);
                
                System.out.print(String.format("%02d.",++idx));
                for(int i:result) {
                    System.out.print(i+",");
                }
                System.out.print(1+",");
                
                Collections.sort(right);
                for(int i:right) {
                    System.out.print(i+",");
                }
                
                System.out.println();
            }
        }
    }
    
    /**
     * 看数字在列表中是否存在
     * @param num
     * @param arr
     * @return
     */
    private static boolean isExist(int num,List<Integer> arr) {
        for(int i:arr) {
            if(num==i) {
                return true;
            }
        }
        
        return false;
    }
}

具体的排列方式：

01.2,1,3,4,5,6,7,
02.3,1,2,4,5,6,7,
03.4,1,2,3,5,6,7,
04.5,1,2,3,4,6,7,
05.6,1,2,3,4,5,7,
06.7,1,2,3,4,5,6,
07.3,2,1,4,5,6,7,
08.4,2,1,3,5,6,7,
09.5,2,1,3,4,6,7,
10.6,2,1,3,4,5,7,
11.7,2,1,3,4,5,6,
12.4,3,1,2,5,6,7,
13.5,3,1,2,4,6,7,
14.6,3,1,2,4,5,7,
15.7,3,1,2,4,5,6,
16.5,4,1,2,3,6,7,
17.6,4,1,2,3,5,7,
18.7,4,1,2,3,5,6,
19.6,5,1,2,3,4,7,
20.7,5,1,2,3,4,6,
21.7,6,1,2,3,4,5,
22.4,3,2,1,5,6,7,
23.5,3,2,1,4,6,7,
24.6,3,2,1,4,5,7,
25.7,3,2,1,4,5,6,
26.5,4,2,1,3,6,7,
27.6,4,2,1,3,5,7,
28.7,4,2,1,3,5,6,
29.6,5,2,1,3,4,7,
30.7,5,2,1,3,4,6,
31.7,6,2,1,3,4,5,
32.5,4,3,1,2,6,7,
33.6,4,3,1,2,5,7,
34.7,4,3,1,2,5,6,
35.6,5,3,1,2,4,7,
36.7,5,3,1,2,4,6,
37.7,6,3,1,2,4,5,
38.6,5,4,1,2,3,7,
39.7,5,4,1,2,3,6,
40.7,6,4,1,2,3,5,
41.7,6,5,1,2,3,4,
42.5,4,3,2,1,6,7,
43.6,4,3,2,1,5,7,
44.7,4,3,2,1,5,6,
45.6,5,3,2,1,4,7,
46.7,5,3,2,1,4,6,
47.7,6,3,2,1,4,5,
48.6,5,4,2,1,3,7,
49.7,5,4,2,1,3,6,
50.7,6,4,2,1,3,5,
51.7,6,5,2,1,3,4,
52.6,5,4,3,1,2,7,
53.7,5,4,3,1,2,6,
54.7,6,4,3,1,2,5,
55.7,6,5,3,1,2,4,
56.7,6,5,4,1,2,3,
57.6,5,4,3,2,1,7,
58.7,5,4,3,2,1,6,
59.7,6,4,3,2,1,5,
60.7,6,5,3,2,1,4,
61.7,6,5,4,2,1,3,
62.7,6,5,4,3,1,2,

END