Java 对元素进行排列组合

àì夳堔傛蜴生んèń 2023-10-01 20:59 28阅读 0赞

#### Java 对元素进行排列组合 ####

*  一、全排列
 *  二、排列
 *  三、组合

## 一、全排列 ##

举例：  
输入：\[0,1,2\]  
输出：\[A, A, A\]  
\[A, A, B\]  
…  
\[C, C, B\]  
\[C, C, C\]

代码实现（[参考链接][Link 1]）

public static Stack<String> stack = new Stack<>();
        public static void main(String[] args) {
        
            //int shu[] = {0,1,2};
            String shu[] = {
        "A","B","C"};
            cycle(shu,3,0);
        }
        /**
         * 3-0     0--> 0
         * 3--1    0--> 0
         * 3---2   0--> 0
         * 3----3  P-->
         * return
         *
         *
         * @param shu 待选择的数组
         * @param tag 要选择多少个次
         * @param cur 当前选择的是第几次
         */
        private static void cycle(String[] shu, int tag, int cur) {
        
            // TODO Auto-generated method stub
            if(cur == tag) {
        
                System.out.println(stack);
                return;
            }
    
            for(int i=0;i<shu.length;i++) {
        
                //压入栈顶
                stack.add(shu[i]);
                //回调
                cycle(shu, tag, cur+1);
                //移除栈顶数据
                stack.pop();
            }
        }

## 二、排列 ##

全排列，即不计重复情况；如果不允许元素重复，则在入栈时去重即可

栈说明：

1.栈位置基于 1 开始，且栈顶为 1
    2.栈内不存在某元素，则返回位置信息为 -1

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54yq5oKf6YGT_size_20_color_FFFFFF_t_70_g_se_x_16]  
修改代码如下，以四选二为例：

import java.util.Stack;
    /**
     * Description: 测试类
     *
     * @Author: zhx & moon hongxu_1234@163.com
     * @Date: 2022-02-25 23:17
     * @version: V1.0.0
     */
    public class Test {
        
    
        public static Stack<String> stack = new Stack<>();
        public static void main(String[] args) {
        
            //int shu[] = {0,1,2};
            String shu[] = {
        "A","B","C","D"};
            cycle(shu,2,0);
        }
        /**
         * 3-0     0--> 0
         * 3--1    0--> 0
         * 3---2   0--> 0
         * 3----3  P-->
         * return
         *
         *
         * @param shu 待选择的数组
         * @param tag 要选择多少个次
         * @param cur 当前选择的是第几次
         */
        private static void cycle(String[] shu, int tag, int cur) {
        
            // TODO Auto-generated method stub
            if(cur == tag) {
        
                System.out.println(stack);
                return;
            }
            for(int i=0;i<shu.length;i++) {
        
                //压入栈顶 栈内不存在该元素时才加入
                if (stack.search(shu[i])<0){
        
                    stack.add(shu[i]);
                    //回调
                    cycle(shu, tag, cur+1);
                    //移除栈顶数据
                    stack.pop();
                }
            }
        }
    }

打印结果

[A, B]
    [A, C]
    [A, D]
    [B, A]
    [B, C]
    [B, D]
    [C, A]
    [C, B]
    [C, D]
    [D, A]
    [D, B]
    [D, C]

## 三、组合 ##

1.选二，就是排列结果除【2】  
2.选三，就是排列结果除【6】

如何输出实际元素选择结果，首先全选或选一个，输出很明显

举例：  
输入：\[1,2,3,4\]  
输出：

四选二：1,2 ---> 1,3 ---> 1,4
           2,3 ---> 2,4
           3,4
    四选三：1,2,3 ---> 1,2,4 ---> 1,3,4
           2,3,4

修改代码如下，以四选三为例：

import java.util.Stack;
    
    /**
     * Description: 测试类
     *
     * @Author: zhx & moon hongxu_1234@163.com
     * @Date: 2022-02-25 23:17
     * @version: V1.0.0
     */
    public class Test {
        
    
        public static Stack<String> stack = new Stack<>();
        public static void main(String[] args) {
        
            String shu[] = {
        "A","B","C","D"};
            cycle(shu,3,0,0);
        }
        /**
         * 3-0     0--> 0
         * 3--1    0--> 0
         * 3---2   0--> 0
         * 3----3  P-->
         * return
         *
         *
         * @param shu 待选择的数组
         * @param tag 要选择多少个次
         * @param has 当前已选多少个
         * @param cur 当前已选到的下标
         */
        private static void cycle(String[] shu, int tag,int has, int cur) {
        
            // TODO Auto-generated method stub
    
            System.out.println("Times_Cur: " + cur);
    
            if(tag == has) {
        
                System.out.println(stack);
                return;
            }
    
            for(int i=cur;i<shu.length;i++) {
        
                //压入栈顶 栈内不存在该元素时才加入
                if (stack.search(shu[i])<0){
        
                    stack.add(shu[i]);
                    //回调
                    cycle(shu, tag, has+1,i);
                    //移除栈顶数据
                    stack.pop();
                }
            }
        }
    }

打印结果（输出 cur 的值，能相对直观展现回调过程）

Times_Cur: 0
    Times_Cur: 0
    Times_Cur: 1
    Times_Cur: 2
    [A, B, C]
    Times_Cur: 3
    [A, B, D]
    Times_Cur: 2
    Times_Cur: 3
    [A, C, D]
    Times_Cur: 3
    Times_Cur: 1
    Times_Cur: 2
    Times_Cur: 3
    [B, C, D]
    Times_Cur: 3
    Times_Cur: 2
    Times_Cur: 3
    Times_Cur: 3

[Link 1]: https://www.cnblogs.com/zzlback/p/10947064.html
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54yq5oKf6YGT_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/cca9cf6b03d24784b32811aa3477fb9f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54yq5oKf6YGT,size_20,color_FFFFFF,t_70,g_se,x_16