[数据结构与算法]java有关排列、组合的算法

package com.test.test02;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import static java.util.stream.Collectors.toList;

/**
 * @author cruder*
 * @date 2022/3/1 21:01
 */
public class Test02 {

    public static void main(String[] args) {
        arrangeAll(Arrays.asList(1,2,3),"");
    }

    static void test001(){
        List<Integer> numbers1 = Arrays.asList(1,2,3);
        List<Integer> numbers2 = Arrays.asList(3,4);
        List<int[]> pairs = numbers1.stream()
                .flatMap(i -> numbers2
                        .stream()
                        .map(j -> new int[]{i, j})
                ).collect(toList());
        pairs.forEach(i->{
            for (int j = 0; j <i.length ; j++) {
                System.out.print(i[j]+" ");
            }
            System.out.println();
        });
    }

    static void test002(){
        List<String> list = Arrays.asList("123456".split(""));
        list.stream()
                .flatMap(str -> list.stream().map(str::concat))
                .flatMap(str -> list.stream().map(str::concat))
                .flatMap(str -> list.stream().map(str::concat))
                .collect(Collectors.toList())
                .forEach(System.out::println);
    }

    /**
     * 排列组合（字符重复排列）<br>
     * 内存占用：需注意结果集大小对内存的占用（list:10位，length:8，结果集:[10 ^ 8 = 100000000]，内存占用:约7G）
     * @param list 待排列组合字符集合
     * @param length 排列组合生成的字符串长度
     * @return 指定长度的排列组合后的字符串集合
     * @author www@yiynx.cn
     */
    public static List<String> permutation(List<String> list, int length) {
        Stream<String> stream = list.stream();
        for (int n = 1; n < length; n++) {
            stream = stream.flatMap(str -> list.stream().map(str::concat));
        }
        return stream.collect(Collectors.toList());
    }

    /**
     * 排列组合(字符不重复排列)<br>
     * 内存占用：需注意结果集大小对内存的占用（list:10位，length:8，结果集:[10! / (10-8)! = 1814400]）
     * @param list 待排列组合字符集合(忽略重复字符)
     * @param length 排列组合生成长度
     * @return 指定长度的排列组合后的字符串集合
     * @author www@yiynx.cn
     */
    public static List<String> permutationNoRepeat(List<String> list, int length) {
        Stream<String> stream = list.stream().distinct();
        for (int n = 1; n < length; n++) {
            stream = stream.flatMap(str -> list.stream()
                    .filter(temp -> !str.contains(temp))
                    .map(str::concat));
        }
        return stream.collect(Collectors.toList());
    }

    /**
     * 递归调用方法
     * @param parameter 需要排列的参数
     * @return 该参数排列所有可能的数组
     *         因其结果可能有数字的重复，所以采用Set去重
     */
    private static Set<String> action(String parameter){
        //如果参数为1，则返回，
        //每次递归参数的长度会减少1，这是递归的最后结点
        if(parameter.length() == 1){
            Set<String> set = new HashSet<String>();
            set.add(parameter);
            return set;
        }
        //方法返回数组
        Set<String> resultList = new HashSet<String>();
        //循环参数，将其分为两段，一段为单个字符，一段为其余的字符串
        for(int i=0;i<parameter.length();i++){
            //单个字符，如果12345需要排列，首先1不动，2345进行排列
            String s = parameter.substring(i,i+1);
            //其余的字符串
            String rest = parameter.substring(0,i)+parameter.substring(i+1);
            //将其余的字符串递归所得到的数组
            Set<String> list = action(rest);
            //将该单个字符与其余字符串的排列拼起来，既完成了以该字符占第一位，其余字符串进行排列的组合
            for(String str : list){
                StringBuilder sb = new StringBuilder(s.length()+str.length());
                sb.append(s);
                sb.append(str);

                if(sb.length() == 6){
                    if(validate(sb.toString())){
                        resultList.add(sb.toString());
                    }
                }else{
                    resultList.add(sb.toString());
                }
            }
        }
        return resultList;
    }

    /**
     *  用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列
     *  如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
     * @param s
     * @return
     */
    private static boolean validate(String s){
        if (s.charAt(2) == '4')
            return false;
        if (s.indexOf("35") >= 0 || s.indexOf("53") >= 0)
            return false;
        return true;
    }

    /**
     * 将数组元素转化为逗号分隔的字符串
     *
     * @param oriList 原始数组
     * @return 字符串
     */
    public static String getStrFromList(List oriList){
        StringBuffer result = new StringBuffer();
        if (oriList == null){
            return result.toString();
        } else {
            for (int i = 0; i < oriList.size(); i++){
                result.append(oriList.get(i));
                if (i != (oriList.size() - 1)){
                    result.append(",");
                }
            }
        }
        return result.toString();
    }


    /**
     * 循环递归获取给定数组元素(无重复)的全排列
     *
     * @param oriList 原始数组
     * @param oriLen 原始数组size
     * @param arrayCombResult 数组排列结果集，可传null或空Set
     * @param preList 记录排列参数，可传null或空List
     * @return 排列结果
     */
    public static Set<String> getArrange(List oriList, int oriLen, Set<String> arrayCombResult, List preList){
        if (oriList == null){
            return arrayCombResult;
        }
        if (arrayCombResult == null){
            arrayCombResult = new HashSet<>();
        }
        if (preList == null){
            preList = new ArrayList();
        }
        for (int i = 0; i < oriList.size(); i++){
            while(preList.size() > 0 && oriList.size() + preList.size() > oriLen){
                preList.remove(preList.size() - 1);
            }
            List arrList = new ArrayList(oriList);
            preList.add(arrList.get(i));
            arrList.remove(i);
            if (arrList.isEmpty()){
                arrayCombResult.add(getStrFromList(preList));
            }else {
                getArrange(arrList, oriLen, arrayCombResult, preList);
            }
        }
        return arrayCombResult;
    }

    /**
     * 循环递归获取给定数组元素(无重复)的所有组合
     *
     * @param oriList 原始数组
     * @param resultSet 元素组合结果，可传null或空set
     * @return 组合结果
     */
    public static Set<String> getCombination(List oriList, Set<String> resultSet) {
        if (oriList == null) {
            return resultSet;
        }
        if (resultSet == null){
            resultSet = new HashSet<>();
        }
        for (int i = 0; i < oriList.size(); i++) {
            List copyList = new ArrayList(oriList);
            resultSet.add(getStrFromList(copyList));
            List removeIList = new ArrayList();
            copyList.remove(i);
            removeIList.addAll(copyList);
            getCombination(removeIList, resultSet);
        }
        return resultSet;
    }


    public static void arrangeAll(List array, String prefix){
        System.out.println(prefix);
        for (int i = 0; i < array.size(); i++) {
            List temp = new LinkedList(array);
            arrangeAll(temp, prefix + temp.remove(i));
        }
    }

    static void test003(){

    }

    static void test004(){

    }

}

package com.test.test02;
import java.util.*;

/**
 *
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split(",");
        Arrays.sort(strs);
        int minNum = sc.nextInt();
        List<String> stringList = new ArrayList<>();
        if(minNum>strs.length){
            System.out.println("None");
        }
        String all="";
        for (int i=minNum;i<strs.length;i++){
            if(i==1){
                List<String> stringList1 = new ArrayList<>();
                all = test1(stringList1,strs);
                stringList.addAll(stringList1);
            }
            if(i==2){
                List<String> stringList2 = new ArrayList<>();

                all = test2(stringList2,strs);
                stringList.addAll(stringList2);
            }
            if(i==3){
                List<String> stringList3 = new ArrayList<>();

                all = test3(stringList3,strs);
                stringList.addAll(stringList3);
            }
            if(i==4){
                List<String> stringList4 = new ArrayList<>();

                all = test4(stringList4,strs);
                stringList.addAll(stringList4);
            }
            if(i==5){
                List<String> stringList5 = new ArrayList<>();

                all = test5(stringList5,strs);
                stringList.addAll(stringList5);
            }
            if(i==6){
                List<String> stringList6 = new ArrayList<>();

                all = test6(stringList6,strs);
                stringList.addAll(stringList6);
            }
            if(i==7){
                List<String> stringList7 = new ArrayList<>();

                all = test7(stringList7,strs);
                stringList.addAll(stringList7);
            }
            if(i==8){
                List<String> stringList8 = new ArrayList<>();
                stringList.addAll(stringList8);
                all = test8(stringList8,strs);
            }
            if(i==9){
                List<String> stringList9 = new ArrayList<>();

                all = test9(stringList9,strs);
                stringList.addAll(stringList9);
            }
        }
        if(minNum!=strs.length){
            stringList.add(all);
        }
        Object[] strings1 = stringList.toArray();
        Arrays.sort(strings1);
        for (int i = 0; i <strings1.length ; i++) {
            System.out.println(strings1[i]);
        }
    }

    static String test10(List<String> stringList,String[] strs){
        String all = "";
        return all;
    }

    static String test9(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    for (int l = k; l <strs.length ; l++) {
                        for (int m = 0; m <strs.length ; m++) {
                            for (int n = 0; n <strs.length ; n++) {
                                for (int o = 0; o <strs.length ; o++) {
                                    for (int p = 0; p <strs.length ; p++) {
                                        for (int q = 0; q <strs.length ; q++) {
                                            stringList.add(strs[i]+","+strs[j]+","+strs[k]+","+strs[l]+","+strs[m]+","+strs[n]+","+strs[o]+","+strs[p]+","+strs[q]);
                                        }
                                    }
                                }
                            }
                        }

                    }
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test8(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    for (int l = k; l <strs.length ; l++) {
                        for (int m = 0; m <strs.length ; m++) {
                            for (int n = 0; n <strs.length ; n++) {
                                for (int o = 0; o <strs.length ; o++) {
                                    for (int p = 0; p <strs.length ; p++) {
                                        stringList.add(strs[i]+","+strs[j]+","+strs[k]+","+strs[l]+","+strs[m]+","+strs[n]+","+strs[o]+","+strs[p]);

                                    }
                                }
                            }
                        }

                    }
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test7(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    for (int l = k; l <strs.length ; l++) {
                        for (int m = 0; m <strs.length ; m++) {
                            for (int n = 0; n <strs.length ; n++) {
                                for (int o = 0; o <strs.length ; o++) {
                                    stringList.add(strs[i]+","+strs[j]+","+strs[k]+","+strs[l]+","+strs[m]+","+strs[n]+","+strs[o]);

                                }
                            }
                        }

                    }
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }


    static String test6(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    for (int l = k; l <strs.length ; l++) {
                        for (int m = 0; m <strs.length ; m++) {
                            for (int n = 0; n <strs.length ; n++) {
                                stringList.add(strs[i]+","+strs[j]+","+strs[k]+","+strs[l]+","+strs[m]+","+strs[n]);

                            }
                        }

                    }
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test5(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    for (int l = k; l <strs.length ; l++) {
                        for (int m = 0; m <strs.length ; m++) {
                            stringList.add(strs[i]+","+strs[j]+","+strs[k]+","+strs[l]+","+strs[m]);

                        }

                    }
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test4(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    for (int l = k; l <strs.length ; l++) {
                        stringList.add(strs[i]+","+strs[j]+","+strs[k]+","+strs[l]);
                    }
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test3(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                for (int k = j+1; k <strs.length ; k++) {
                    stringList.add(strs[i]+","+strs[j]+","+strs[k]);
                }
            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test2(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            for (int j = i+1; j <strs.length ; j++) {
                stringList.add(strs[i]+","+strs[j]);

            }
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }

    static String test1(List<String> stringList,String[] strs){
        String all = "";
        for (int i = 0; i <strs.length ; i++) {
            stringList.add(strs[i]);
            if(i==0){
                all+=strs[i];
            }else {
                all+=","+strs[i];
            }
        }
        return all;
    }
}