java递归实现排列、组合算法

青旅半醒 2022-03-15 12:35 262阅读 0赞

项目需要，特此记录

/*
    *@ input:输入List
    *@ result :排列或组合输出结果
    *@ temp: 存储某种排列或组合方式
    *@ k: input.lengh个元素中选取k个元素
    /

package com.cooooode;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Demo {
        public static void main(String[] args) {
            List<Character> input=new ArrayList<>(Arrays.asList('a','b','c','d','e','f','g'));
            List<List<Character>> permutationResult=Permutation(input,4);
            for(List<Character> item:permutationResult){
                System.out.println(item);
            }
            System.out.println(permutationResult.size());
            List<List<Character>> combinationResult=Combination(input,4);
            for(List<Character> item:combinationResult){
                System.out.println(item);
            }
            System.out.println(combinationResult.size());
        }
        public static<E> List<List<E>> Permutation(List<E> input,int k){
    		if(input.size()<k) return null;
            List<List<E>> result=new ArrayList<>();
            /*
            //        先组合后排列
            List<List<E>> combination=Combination(input,k);
            for(List<E> item: combination){
                Permutation(item,result,new ArrayList<>(),item.size());
            }*/
            //        直接排列
            Permutation(input,result,new ArrayList<E>(),k);
            return result;
        }
        //    排列
        public static<E> void Permutation(List<E> input,List<List<E>> result,List<E> temp,int k){
            if(temp.size()==k) {
                System.out.println(temp);
                result.add(temp);
                return;
            }
            for(int i=0;i<input.size();i++){
                List<E> copyInput=new ArrayList<>(input);
                List<E> copyTemp=new ArrayList<>(temp);
                copyTemp.add(input.get(i));
                copyInput.remove(i);
                Permutation(copyInput,result,copyTemp,k);
            }
        }
        public static<E> List<List<E>> Combination(List<E> input,int k){
            if(input.size()<k) return null;
            List<List<E>> result=new ArrayList<>();
            Combination(input,result,new ArrayList<>(),0,k,k);
           //Combination(input,result,new ArrayList<>(),k);
            return result;
        }
        //    组合法一
        public static<E> void Combination(List<E> input, List<List<E>> result, List<E> temp, int k){
            if(temp.size()==k) {
                result.add(temp);
                return;
            }
            for(int i=0;i<input.size();i++){
                List<E> copyInput=new ArrayList<>(input);
                List<E> copyTemp=new ArrayList<>(temp);
                copyTemp.add(copyInput.get(i));//遍历添加元素
                for(int j=i;j>=0;j--)
                    copyInput.remove(j);//去除前元素
                Combination(copyInput,result,copyTemp,k);
            }
        }
        //    组合法二
        public static<E> void Combination(List<E> input, List<List<E>> result, List<E> temp, int start,int end,int k){
            if(temp.size()==k) {
                result.add(temp);
                return;
            }
            for(int i=start;i<input.size()-end+1;i++){
                List<E> copyTemp=new ArrayList<>(temp);
                copyTemp.add(input.get(i));
                Combination(input,result,copyTemp,i+1,end-1,k);
            }
        }
    }

排列和组合算法类似，主要区别在于排列算法中删除循环当前元素

for(int i=0;i<input.size();i++){
                List<E> copyInput=new ArrayList<>(input);
                List<E> copyTemp=new ArrayList<>(temp);
                copyTemp.add(input.get(i));
                copyInput.remove(i);//删除当前元素
                Permutation(copyInput,result,copyTemp,k);
            }

而组合算法中删除的是循环当前元素前面所有元素

for(int i=0;i<input.size();i++){
                List<E> copyInput=new ArrayList<>(input);
                List<E> copyTemp=new ArrayList<>(temp);
                copyTemp.add(copyInput.get(i));
                for(int j=i;j>=0;j--)
                    copyInput.remove(j);//删除当前元素前面所有元素
                Combination(copyInput,result,copyTemp,k);
            }

组合方法二比较法一，节省内存空间，利用索引确定迭代遍历元素；

for(int i=start;i<input.size()-end+1;i++){
                List<E> copyTemp=new ArrayList<>(temp);
                copyTemp.add(input.get(i));
                Combination(input,result,copyTemp,i+1,end-1,k);
            }