多个数组间元素排列组合问题求解(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);

    }



  • 2020-12-13 19:44:07

    运行中的docker实例添加-v挂载文件夹

    之前有人问我Docker容器启动之后还能否再挂载卷,考虑到mnt命名空间的工作原理,我一开始认为这很难实现。不过现在Petazzoni通过使用nsenter和绑定挂载实现了这个需求,你可以在你的环境中测试下。

  • 2020-12-13 19:49:32

    Docker run命令详解

    命令格式:docker run [OPTIONS] IMAGE [COMMAND] [ARG...] Usage: Run a command in a new container 中文意思为:通过run命令创建一个新的容器(container)

  • 2020-12-13 20:15:43

    解决gitlab限制上传文件大小的问题

    服务端的限制有两个地方一个是gitlab本身,另外一个是gitlab使用的nginx。 gitlab本身也是很好解决的,使用管理员用户登录gitlab在设置Account and limit中加大Maximum attachment size (MB)和Maximum push size (MB)即可解决 nginx的话修改gitlab.rb这个文件中

  • 2020-12-14 15:06:50

    youtube-dl视频下载神器

    youtube-dl 是一款命令行下的视频下载工具,看着名称像是 YouTube 下载工具,其实这款工具不仅支持 YouTube ,还支持非常多的视频网站,比如优酷、爱奇艺、 bilibili 等,在写这篇日志的时候,暂时不支持腾讯视频。

  • 2020-12-15 20:06:43

    更多WebTorrent例子

    WebTorrent是第一个运行在浏览器的Torrent客户端。是的,没错。就是浏览器! 它完全是用JavaScript编写的,并使用WebRTC实现了真正的点对点传输。不需要浏览器插件、扩展或安装。 使用开放的Web标准,WebTorrent将网站用户连接在一起,形成一个分布式的、分散的Browser-to-browser网络,以实现高效的文件传输。