多维数组的组合排序算法

一,聊骚:

我是一个喜欢直奔主题的人,不喜欢把时间浪费到废话上,因为这也是在浪费读者到时间,那为什么我今天一反常态,要说点聊骚的话呢?

缘由是这样的,作为一个自学成才(其实还没有成才)的前端人员来说,前端之路是多么的坎坷,面对大量的前端知识,面对如雨后春笋般的前端框架的兴起,面对nodejs在前端与后端之间的连接的应用,

此时的前端再也不是几年前的那个前端了,有太多的框架要去学,有太多的前端知识要去研究,学习,这样难免会让人失去方向,学的东西也很杂,为了适应现在的对前端人员的要求,你就不得不撒开网去

探索,导致的结果就是,你好像什么都接触过,感觉什么都懂,但是如果要你说出一个所以然来,好像又什么都不懂,这才是前端学习最可怕的,浮于表面,没有真正深入了解其中的原理,有人会说,现在的技术学习曲线那么陡,要学的知识那么多,哪有那么多时间去学呢?

回答这个问题,我得先说,我失业了,就如同我前面说的一样,我只是浮于表面,没有真正沉下去,那怎么才能学好技术呢?根据牛人的指导,大致是在技术选型上,选择适合自己的,比如说前端框架,angularjs,reactjs,backbonejs,vuejs等等,选择一个自己觉得比较好上手的,然后搭配一个打包工具,比如webpack,gulp,grunt等等,多去深入理解它的实现原理,编写的思想,总之,多看,

多写(这才是重点),多研究,然后把自己的心得感悟,以笔记或者博客的形式记录下来,让牛人们帮你喷喷,这样既可以加深印象,还可以和牛人一起学习,算了,不说了,这其实是写给我看的。

二,正题:

言归正传,今天我们要讲的是一个什么命题呢?

命题:多维数组的排列组合 或 多个数组之间的排列组合

命题场景:

现在有一批手机,其中颜色有['白色','黑色','金色'];内存大小有['16G','32G','64G'],版本有['移动','联通','电信'],要求写一个算法,实现[['白色','16G','移动'], ['白色','16G','联通'] ...]这样的组合,扩张,如果后面还有参数,比如再加一个['国行','港版'],不改程序一样可以执行!

不知道要实现的需求大家听懂了没有,下面我会一步步实现,教大家怎么写:

最后得到的结果是一个数组里面包含若干个数组,看着挺复杂的,我们先实现一个简化版的,数组里面不是数组,而是字符串连接的结果,嗯,先一步步来吧:

第一步,想想通过什么技术来实现,你看这数组之间不断的重组,很容易想到用回调函数,一遍一遍的执行,大致知道用什么技术,接下来就是写思路了,看看下面:

// 执行组合排列的函数     
function doExchange(arr)
    {}
//执行     
var arr = [
    ['a', 'b', 'c'],
    [1, 2, 3],
    ['x', 'y', 'z']
];
var arr1 = [
    ['a', 'b', 'c']
]; 
//doExchange(arr);    
console.log(doExchange(arr));

呐,我们建一个函数doExchange(),表示我们执行排序的主函数,然后当执行arr的时候,输出['a1x','a1y' ...]这样的结果,如果是arr1呢?我们需要输出['a','b','c'],这好理解哈,现在的重点就是这个主函数了,下面主要讲主函数的实现过程

// 执行组合排列的函数
function doExchange(arr)
{
    var len = arr.length;
    // 当数组大于等于2个的时候
    if(len >= 2)
    {}
    else
    {
        return arr[0];
    }
}

我们的思路是,当参数里面的数组长度大于2个,比如2个,3个或更多,就执行我们的组合代码,否则只有一个,就直接输出来呗

如果是大于2个呢?我们的思路是先进行第一个和第二个的合并,网上有一种实现方式是,用多层for循环来嵌套,最终得到组合的值,这种估计大家也能感觉到,两三个还可以,多了就呵呵了,这里只是提一下,因为前两个比较好获取,合并之后呢,就相当于是

2个数组合并成一个数组,然后这个数组再放倒参数数组中第一个位置,把原来前两个去掉,相当于是用这个数组替换前两个,没听懂哈,没关系,我们直接看代码:

if(len >= 2)
{
    // 第一个数组的长度             
    var len1 = arr[0].length;
    // 第二个数组的长度             
    var len2 = arr[1].length;
    // 2个数组产生的组合数             
    var lenBoth = len1 * len2;
    //  申明一个新数组,做数据暂存             
    var items = new Array(lenBoth);
    // 申明新数组的索引             
    var index = 0;
    // 2层嵌套循环,将组合放到新数组中
    for(var i = 0; i < len1; i++)
    {
        for(var j = 0; j < len2; j++)
        {
            items[index] = arr[0][i] + arr[1][j];
            index++;
        }
    }
}

呐,这里我们先获取第一个和第二个数组的长度,然后计算出它们有多少种组合方式,然后新建一个暂存的数组,用来存我们组合得到的结果,后面就是用双层循环,做字符串连接,放到暂存数组中,没什么好说的

我们的到了前两个的组合结果,依据我们的思路,是要把它和原来数组合并成一个新数组

// 第一个数组的长度             
var len1 = arr[0].length;
// 第二个数组的长度             
var len2 = arr[1].length;
// 2个数组产生的组合数            
var lenBoth = len1 * len2;
//  申明一个新数组,做数据暂存   
var items = new Array(lenBoth);
// 申明新数组的索引             
var index = 0;
// 2层嵌套循环,将组合放到新数组中             
for(var i = 0; i < len1; i++)
{
    for(var j = 0; j < len2; j++)
    {
        items[index] = arr[0][i] + arr[1][j];
        index++;
    }
}
// 将新组合的数组并到原数组中            
var newArr = new Array(len - 1);
for(var i = 2; i < arr.length; i++)
{
    newArr[i - 1] = arr[i];
}
newArr[0] = items;

整体的思路就是这样,得到的新数组就是剩下的未组合的数组了,到这里大家应该就豁然开朗了,然后使用递归再次调用这个过程,这样不断组合成新数组,那这个新数组当参数时,如果数组的长度等于1了,就说明组合完了,就会执行后面的else语句,输出出来。

整体代码贴出来感受一下:

// 执行组合排列的函数     
function doExchange(arr)
    {
        var len = arr.length;
        // 当数组大于等于2个的时候         
        if(len >= 2)
        {
            // 第一个数组的长度             
            var len1 = arr[0].length;
            // 第二个数组的长度       
            var len2 = arr[1].length;
            // 2个数组产生的组合数         
            var lenBoth = len1 * len2;
            //  申明一个新数组,做数据暂存         
            var items = new Array(lenBoth);
            // 申明新数组的索引           
            var index = 0;
            // 2层嵌套循环,将组合放到新数组中        
            for(var i = 0; i < len1; i++)
            {
                for(var j = 0; j < len2; j++)
                {
                    items[index] = arr[0][i] + arr[1][j];
                    index++;
                }
            }
            // 将新组合的数组并到原数组中             
            var newArr = new Array(len - 1);
            for(var i = 2; i < arr.length; i++)
            {
                newArr[i - 1] = arr[i];
            }
            newArr[0] = items;
            // 执行回调             
            return doExchange(newArr);
        }
        else
        {
            return arr[0];
        }
    }
    //执行     
var arr = [
    ['a', 'b', 'c'],
    [1, 2, 3],
    ['x', 'y', 'z']
];
var arr1 = [
    ['a', 'b', 'c']
];
//doExchange(arr);     
console.log(doExchange(arr));

我们简化版的组合算是完成了,可能也会有类似的需求,但是我们今天要讲的不是这样的需求,而是里面的每一个组合要是一个数组,这个怎么实现呢?

突破点应该就在字符串连接那块了,原来是用的字符串连接,如果我们改成数组连接,不就行了吗?试试:

for(var i = 0; i < len1; i++)
{
    for(var j = 0; j < len2; j++)
    {
        if(arr[0][i] instanceof Array)
        {
            items[index] = arr[0][i].concat(arr[1][j]);
        }
        else
        {
            items[index] = [arr[0][i]].concat(arr[1][j]);
        }
        index++;
    }
}

其他地方都没有改,就只是改了这里,但是这里第一次是要做数组判断的,因为刚开始是字符串,要转换成数组才能连接,这里注意一下,最终的代码如下:

function doExchange(arr)
    {
        var len = arr.length;
        // 当数组大于等于2个的时候         
        if(len >= 2)
        {
            // 第一个数组的长度            
            var len1 = arr[0].length;
            // 第二个数组的长度           
            var len2 = arr[1].length;
            // 2个数组产生的组合数         
            var lenBoth = len1 * len2;
            //  申明一个新数组            
            var items = new Array(lenBoth);
            // 申明新数组的索引           
            var index = 0;
            for(var i = 0; i < len1; i++)
            {
                for(var j = 0; j < len2; j++)
                {
                    if(arr[0][i] instanceof Array)
                    {
                        items[index] = arr[0][i].concat(arr[1][j]);
                    }
                    else
                    {
                        items[index] = [arr[0][i]].concat(arr[1][j]);
                    }
                    index++;
                }
            }
            var newArr = new Array(len - 1);
            for(var i = 2; i < arr.length; i++)
            {
                newArr[i - 1] = arr[i];
            }
            newArr[0] = items;
            return doExchange(newArr);
        }
        else
        {
            return arr[0];
        }
    }
    //     
var arr = [
    ['a', 'b', 'c'],
    [1, 2, 3],
    ['x', 'y', 'z'],
    ['手机']
];
var arr1 = [
    ['a', 'b', 'c']
];
console.log(doExchange(arr));

我后面又加了一个手机,同样是可以实现的,到这里就算死写完了。

 

三,总结:

给个总结吧,这个算法刚开始想想,感觉挺复杂的,这么多数组要排列组合,但是我们将它化繁为简,比如说就当只有2个数组的组合,是不是就简单多了,这个实现了,然后考虑多组的,这样世界就清静了!还是那句话,还是多写吧!

欢迎转载,原创不易,转载时请注明出处,谢谢!

 

来源:博客园

—— 完 ——
相关推荐
评论

立 为 非 似

中 谁 昨 此

宵 风 夜 星

。 露 , 辰

文章点击榜

细 无 轻 自

如 边 似 在

愁 丝 梦 飞

。 雨 , 花