文档章节

多个数组排列问题

chro008
 chro008
发布于 06/19 17:10
字数 1096
阅读 10
收藏 0

有时候会有需求 从N个数组个各取1个元素组成新数组,问有多少种可能,分别是什么?(这里假设不涉及重复元素和顺序影响)

类似 [a,b,c,d],[1,2],[A,B,F] 3个数组个各取一个元素组成新数组,共计24种可能,结果分别如下:

[a,1,A],[a,1,B],[a,1,F],[a,2,A],[a,2,B],[a,2,F],[b,1,A],[b,1,B]......[d,2,A],[d,2,B],[d,2,F].

那如何用程序来完成这个数学问题呢?下面先介绍思路,再用java代码尝试code。

每次从3个数组中各取一个元素,取元素的下标初始默认分别是0->(0,0,0),即:第一个数组是"a",第二个数组是"1",第三个数组是"A"; 下一个新数组来源的下标呢?前2个还是0,第三个加1->(0,0,1),同理,再下一个呢?(0,0,2),再下一个呢? 是0,0,3吗?

这里需要注意一下,当取元素的数组的下标越界(>=当前数组的长度)时,我们需要将当前元素的数组的下标置为0,前一个数组的下标加1,所以(0,0,2)后面一个下标应该是(0,1,0);后面规律就一样了。

看这个过程像什么呢?是不是类似进制数+1的过程?

如果是10进制的,2个数组就类似组成两位数,3个数组类似组成3位数。可能性= 10*10*...*10,有多少个数组就有10N种可能

如果是2进制的,即,每个源数组都有2个元素,那可能性=2*2*...*2 有多少个数组就有2N种可能;

现在数组长度是不规律的,可能性= 每个数组元素个数乘积,上方示例可能=4*2*3=24种;

知道了过程和原理开始撸代码吧:

给出的参数就是1个集合,集合的每个元素是1个数组

List<String[]> originalList

首先需要2个临时变量数组,分别存放原数组取数的下标和原数组的长度

int[] tempIndexArr = new int[originalList.size()];

int[] tempLengthArr = new int[originalList.size()];

需要1个集合存放新组成的数组

List<String[]> combineList = new ArrayList<>();

需要一个是否完成遍历的flag

boolean completeFlag = false;

最核心的逻辑,其实也很简单,就是取下标索引:

int changeIndex = originalList.size() - 1;

boolean isRightIndex = false;

while (!isRightIndex) {

    tempIndexArr[changeIndex] += 1;

    if(tempIndexArr[changeIndex] >= tempLengthArr[changeIndex]) {

        tempIndexArr[changeIndex--] = 0;

    } else {

        isRightIndex = true;

    }

}

取到了下标索引,从原集合中根据下标索引取数组成新数组放到新集合中

String[] newItem = new String[originalList.size()];

for (int i = 0; i < originalList.size() ; i++) {

    newItem[i] = originalList.get(i)[tempIndexArr[i]];

}

combineList.add(newItem);

基本过程就结束了。 不过这里需要增加一个判断 就是是否遍历完了,判断逻辑是 下标都已经到了最大值,完成代码、测试和打印结果如下

package work;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.lang.StringUtils;

/**
 * @author lixiaoming
 * @date 2019/6/19 16:53
 */
public class CombineTest {

    public static void main(String[] args) {
        List<String[]> originalList = new ArrayList<>();
        originalList.add(new String[] {"a", "b", "c", "d"});
        originalList.add(new String[] {"1", "2"});
        originalList.add(new String[] {"A", "B", "F"});

        List<String[]> combineList = getCombineList(originalList);

        System.out.println("组成的新集合共有" + combineList.size() + "个数组");

        combineList.forEach(s-> {
            System.out.println(StringUtils.join(s, ","));
        });
    }

    private static List<String[]> getCombineList(List<String[]> originalList) {
        int originalSize = originalList.size();
        int[] tempIndexArr = new int[originalSize];
        tempIndexArr[originalSize - 1] = -1;
        int[] tempLengthArr = new int[originalSize];
        for (int i = 0; i < originalSize ; i++) {
            tempLengthArr[i] = originalList.get(i).length;
        }

        List<String[]> combineList = new ArrayList<>();
        boolean completeFlag = false;

        while(!completeFlag) {
            int changeIndex = originalList.size() - 1;
            boolean isRightIndex = false;
            while (!isRightIndex) {
                tempIndexArr[changeIndex] += 1;
                if(tempIndexArr[changeIndex] >= tempLengthArr[changeIndex]) {
                    if(changeIndex == 0) {
                        isRightIndex = true;
                        completeFlag = true;
                    } else {
                        tempIndexArr[changeIndex--] = 0;
                    }
                } else {
                    isRightIndex = true;
                }
            }
            if(isRightIndex && !completeFlag) {
                String[] newItem = new String[originalList.size()];
                for (int i = 0; i < originalList.size() ; i++) {
                    newItem[i] = originalList.get(i)[tempIndexArr[i]];
                }
                combineList.add(newItem);
            }
        }

        return combineList;
    }

}



打印结果如下:

组成的新集合共有24个数组

a,1,A

a,1,B

a,1,F

a,2,A

a,2,B

a,2,F

b,1,A

b,1,B

b,1,F

b,2,A

b,2,B

b,2,F

c,1,A

c,1,B

c,1,F

c,2,A

c,2,B

c,2,F

d,1,A

d,1,B

d,1,F

d,2,A

d,2,B

d,2,F

Process finished with exit code 0

© 著作权归作者所有

chro008

chro008

粉丝 5
博文 46
码字总数 19512
作品 0
海淀
程序员
私信 提问
47. Permutations II

使用递归算法特性:必须的终止条件子问题比原来的问题小子问题可以再递归求解子问题的解能够组成大问题的解 a bc b ac c ba

datacube
2016/07/05
5
0
程序员必备算法——排列组合

程序员必备算法——排列组合 [TOC] 还记得排列组合吗? 在高中的时候最常接触的莫过于排列组合了,毕竟高考必考的嘛。我们先来回忆下这两个的公式是啥: 如果看到这个还有一丢丢的印象,说明...

窗边的扁豆
2017/10/07
0
0
PHP之新手自学基础知识(三)——数组篇

数组是什么? 数组是一个能在单个变量中存储多个值的特殊变量。 如果一个项目清单(例如:手机名字的清单),将其存储到单个变量中如下所示: 然而,如果您想要遍历变量并找出特定的一个呢?...

天谴残魂
2018/01/04
0
0
js笔记二十之Array数组的查询,拼接,转字符串,排列(序)

数组查询 slice 数组的查询 参数: slice(n,m) 从索引n开始找到索引m处(不包含m) 返回值: 把找到的部分以一个新数组返回 原来数组不变 slice(n) 从索引n找到末尾 slice(0)或slice() 数组克隆,...

uplyw
2018/05/14
0
0
PHP学习之路之记录

一、基础知识: 1、变量区分大小写 2、只能包含字母、数字和下划线,并且不能以数字开头,不能包含空格 3、变量在第一次赋值的时候被创建 变量作用域: 1、local 局部变量 2、global 全局变量...

拜拜佛
2016/09/24
28
2

没有更多内容

加载失败,请刷新页面

加载更多

秒杀系统思路

业务分析 技术挑战 请求响应要快:无论成功失败,需要尽快返回给用户 架构设计   前端:静态化   站点层:限制请求数   服务层:乐观锁写缓存   数据库CAP:读写高可用,一致性,扩容...

雷开你的门
31分钟前
11
0
最全的教育行业大数据解决方案,个个针对痛点

大数据的悄然兴起也带动了教育行业的革新,移动教育、云课堂等的出现,使得教育行业再次成为了可以中长期保持高景气的行业。然而,初涉数据领域的教育行业同时也面临着相当大的难题,还需要更...

朕想上头条
35分钟前
7
0
预约模块设计分析

1.预约功能描述: 预约是小程序中常见的一种商品管理系统,商家可根据商品或服务的特性,灵活设置预约细节,为用户提供线上预约服务,如场地预约,商品预定等,实现高效经营。 预约场景: ...

鱼煎
38分钟前
5
0
阿里云日志服务构建网站实时分析大盘实战

场景分析 挖掘数据价值是当前企业级网站共同面临的问题。买买网是一个电商平台网站,每天拥有大量的用户访问和购买记录。为了引导用户直接消费,提升购买率和转化率,不同的用户类别需要推荐...

阿里云官方博客
39分钟前
5
0
TL665xF-EasyEVM开发板硬件处理器、NAND FLASH、RAM

广州创龙结合TI KeyStone系列多核架构TMS320C665x及Xilinx Artix-7系列FPGA设计的TL665xF-EasyEVM开发板是一款DSP+FPGA高速大数据采集处理平台,其底板采用沉金无铅工艺的6层板设计,适用于高...

Tronlong创龙
43分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部