多个数组间元素排列组合问题求解(Java实现),可用于商品规格

2019-09-18 22:21:43

参考地址 多个数组间元素排列组合问题求解(Java实现)

以前还整理过一个js的,下次读到了可以写过来。


求多个数组之间元素的排列组合问题,方法有两个:递归法、循环法。

首先应该认识到的是:


所有可以用递归实现的操作都可以转化为用while、for等循环实现。

递归法

优缺点:

数组数量不太多时用递归法确实使程序比较简洁,数组数量太多时递归函数栈过大,有可能导致运行时栈溢出。而且相对常用的算法如普通循环等,运行效率较低。


实现代码一

/**

     * 写法一,递归计算所有组合

     * @param inputList 所有数组的列表

     * */

    public List<String> combination(List<String> inputList){

        List<String> resList = new ArrayList<>();

        combinationInt(inputList, resList, 0, 

                new char[inputList.size()]);

        return resList;

    }


    private void combinationInt(List<String> inputList, List<String> resList,

            int ind, char[] arr) {

        if(ind == inputList.size()){

            resList.add(new String(arr));

            return;

        }

        for(char c: inputList.get(ind).toCharArray()){

            arr[ind] = c;

            combinationInt(inputList, resList, ind + 1, arr);

        } 

    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

测试程序

//测试部分

    public static void main(String[] args) {

        List<String> list = new ArrayList<>();

        list.add("ab");

        list.add("12");

        list.add("AB");

        List<String> result=combination(list);

        System.out.println("组合结果:");

        for (String string : result) {

            System.out.println(string);

        }   

    }

1

2

3

4

5

6

7

8

9

10

11

12

实现代码二

/**

     * 写法二,递归计算所有组合

     * @param inputList 所有数组的列表,数组用List<Integer>存储

     * @param beginIndex 代表每一个数组的在inputList中的索引

     * @param arr 用于保存每一次递归生成的组合

     * */

    public void calculateCombination(List<List<Integer>> inputList, int beginIndex, int[] arr) {

        if(beginIndex == inputList.size()){

            //在这里进行你自己的处理,比如打印组合的结果

            for (int i : arr) {

                System.out.print(i+", ");

            }

            System.out.println();

            return;

        }

        for(int c: inputList.get(beginIndex)){

            arr[beginIndex] = c;

            calculateCombination(inputList, beginIndex + 1, arr);

        }

    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

测试程序

//测试部分

    public static void main(String[] args) {

        List<Integer> list1 = new ArrayList<>();

        list1.add(0);

        list1.add(1);

        list1.add(2);

        List<Integer> list2 = new ArrayList<>();

        list2.add(3);

        list2.add(4);

        list2.add(5);

        List<Integer> list3 = new ArrayList<>();

        list3.add(6);

        list3.add(7);

        list3.add(8);

        List<List<Integer>> allList = new ArrayList<>();

        allList.add(list1);

        allList.add(list2);

        allList.add(list3);

        calculateCombination(allList, 0, new int[allList.size()]);  

    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

循环法

优缺点:

采用循环方式程序编写较递归法略复杂,但是执行效率高,不管数组数量多少,都不会发生栈溢出。


代码

/**

     * 算法二,非递归计算所有组合

     * @param inputList 所有数组的列表

     * */

    public void calculateCombination(List<List<Integer>> inputList) {

        List<Integer> combination = new ArrayList<Integer>();

        int n=inputList.size();

        for (int i = 0; i < n; i++) {

            combination.add(0);

        }

        int i=0;

        boolean isContinue=false;

        do{

        //打印一次循环生成的组合

            for (int j = 0; j < n; j++) {

                System.out.print(inputList.get(j).get(combination.get(j))+", ");

            }

            System.out.println();


            i++;

            combination.set(n-1, i);

            for (int j = n-1; j >= 0; j--) {

                if (combination.get(j)>=inputList.get(j).size()) {

                    combination.set(j, 0);

                    i=0;

                    if (j-1>=0) {

                        combination.set(j-1, combination.get(j-1)+1);

                    }

                }

            }

            isContinue=false;

            for (Integer integer : combination) {

                if (integer != 0) {

                    isContinue=true;

                }

            }

        }while (isContinue);

    }

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

31

32

33

34

35

36

37

38

测试程序

//测试部分

    public static void main(String[] args) {

        List<Integer> list1 = new ArrayList<>();

        list1.add(0);

        list1.add(1);

        list1.add(2);

        List<Integer> list2 = new ArrayList<>();

        list2.add(3);

        list2.add(4);

        list2.add(5);

        List<Integer> list3 = new ArrayList<>();

        list3.add(6);

        list3.add(7);

        list3.add(8);

        List<List<Integer>> allList = new ArrayList<>();

        allList.add(list1);

        allList.add(list2);

        allList.add(list3);

        calculateCombination(allList);

    }



  • 2019-05-25 14:54:50

    commit your changes or stash them before you can merge

    Your local changes to the following files would be overwritten by merge:         protected/config/main.php Please, commit your changes or stash them before you can merge. --------------------- 作者:陈小峰_iefreer 来源:CSDN 原文:https://blog.csdn.net/iefreer/article/details/7679631 版权声明:本文为博主原创文章,转载请附上博文链接!

  • 2019-05-27 10:43:34

    IntelliJ IDEA中C盘文件过大怎么办

    当我在D:\ 安装完IDEA9.0之后,建立了一个工程,发现C:\Users\Administrator\.IntelliJIdea90 竟然增大到了500+M,并且随着使用在逐渐增大,这样占用系统盘资源是非常让人不爽的,那么如何将其修改到其他路径呢?

  • 2019-05-28 13:33:20

    BRVAH+MTRVA,复杂?不存在的

    言归正传,这样的一个首页,我们需要做怎么样的基础工作呢?或者说,碰到以后更复杂的页面我们应该怎么做?这里小提示下,不要再用什么类似ScrollView的这种东西了,诶,好像说的有点绝对,尽量不要用,这不是谷歌想要看到的,5.0谷歌推出了RecyclerView,从它的整个设计架构来看,简直就是为这而生的。而RecyclerView的视图是通过Adapter来渲染的。原始的Adapter,让人很蛋疼,重复工作太多,我们应该要有封装的思想,把最需要的部分提供出来,其它不用管。

  • 2019-05-29 14:19:19

    解决Git中fatal: refusing to merge unrelated histories

    Git的报错 在使用Git的过程中有时会出现一些问题,那么在解决了每个问题的时候,都需要去总结记录下来,下次不再犯。 一、fatal: refusing to merge unrelated histories 今天在使用Git创建项目的时候,在两个分支合并的时候,出现了下面的这个错误。

  • 2019-05-29 15:47:51

    撤销commit

    在git push的时候,有时候我们会想办法撤销git commit的内容