2

前端电商 sku 的全排列算法

 2 years ago
source link: https://segmentfault.com/a/1190000040834064
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

前端电商 sku 的全排列算法

需求

需求描述起来很简单,有这样三个数组:

let names = ["iPhone",'iPhone xs']

let colors = ['黑色','白色']

let storages = ['64g','256g']

需要把他们的所有组合穷举出来，最终得到这样一个数组：

[

  ["iPhone X", "黑色", "64g"],

  ["iPhone X", "黑色", "256g"],

  ["iPhone X", "白色", "64g"],

  ["iPhone X", "白色", "256g"],

  ["iPhone XS", "黑色", "64g"],

  ["iPhone XS", "黑色", "256g"],

  ["iPhone XS", "白色", "64g"],

  ["iPhone XS", "白色", "256g"],

]

由于这些属性数组是不定项的,所以不能简单的用三重的暴力循环来求解了

思路

如果我们选用递归溯法来解决这个问题，那么最重要的问题就是设计我们的递归函数

思路分解

以上文所举的例子来说,比如我们目前的属性数组就是 names,colors,storages,首先我们会处理names数组
很显然对于每个属性数组 都需要去遍历它 然后一个一个选择后再去和下一个数组的每一项进行组合

我们设计的递归函数接收两个参数

  • index 对应当前正在处理的下标,是names还是colors 或者storage。
  • prev 上一次递归已经拼接成的结果 比如['iphoneX','黑色']

进入递归函数:

  1. 处理属性数组的下标0:假设我们在第一次循环中选择了iphone XS 那此时我们有一个未完成的结果状态,假设我们叫它prev,此时prev = ['iphone Xs']。
  2. 处理属性数组的下标1: 那么就处理到colors数组的了,并且我们拥有prev,在遍历colors的时候继续递归的去把prev 拼接成prev.concat(color),也就是['iphoneXs','黑色'] 这样继续把这个prev交给下一次递归
  3. 处理属性数组的下标2: 那么就处理到storages数组的了 并且我们拥有了 name+ color 的prev,在遍历storages的时候继续递归的去把prev拼接成prev.concat(storage) 也就是['iPhoneXS','黑色','64g'],并且此时我们发现处理的属性数组下标已经达到了末尾，那么就放入全局的结果变量res中，作为一个结果

编码实现

let names = ['iphoneX',"iPhone XS"]

let colors = ['黑色','白色']

let storages = ['64g','256g']

let combine = function(...chunks){

    let res = []

    let helper = function(chunkIndex,prev){

        let chunk = chunks[chunkIndex]

        let isLast = chunkIndex === chunks.length -1

        for(let val of chunk){

            let cur = prev.concat(val)

            // ['iphoneX','黑色','64g'],['iphoneX','黑色','256g'],['iphoneX','白色','64g']

            if(isLast){

                // 如果已经处理到数组的最后一项 则把拼接的结果放入返回值中

                res.push(cur)

            }else{

                helper(chunkIndex+1,cur)

            }

        }

    }

    //从属性数组下标为0开始处理

    // 并且此时的prev是一个空数组

    helper(0,[])

    return res

}

console.log(combine(names,colors,storages));

["iphoneX", "黑色", "64g"]

["iphoneX", "黑色", "256g"]

["iphoneX", "白色", "64g"]

["iphoneX", "白色", "256g"]

["iPhone XS", "黑色", "64g"]

["iPhone XS", "黑色", "256g"]

["iPhone XS", "白色", "64g"]

["iPhone XS", "白色", "256g"]

万能模板

给定两个整数n和k 返回1...n中所有可能的k个数的组合
输入: n = 4, k = 2
输出:

[

  [2,4],

  [3,4],

  [2,3],

  [1,2],

  [1,3],

  [1,4],

]

解答

let combine = function (n,k){

    let ret = []

    let helper = (start,prev)=>{

        let len = prev.length

        if(len === k){

            ret.push(prev)

            return //[[1,2]]

        }

        for(let i = start;i<=n;i++){

            helper(i+1,prev.concat(i))

            //helper(2,[1]) [1,2]

            //helper(3,[1]), [1,3]

            //helper(4,[1]) [1,4]

            //helper(3,[2])  [2,3]

            //helper(4,[2])[2,4]

            // helper(4,[3])[3,4]

        }

    }

    helper(1,[])

    return ret

}
  • 可以看出这题和我们求解电商排列组合的代码竟然如此相似 只需要设计一个接受start排列起始位置,prev上一次拼接结果为参数的递归helper函数
  • 然后对于每一个起点下标start,先拼接上start位置对应的值，再不断的再以其他剩余的下标作为起点去做下一次拼接。
  • 当prev这个中间状态的拼接数组到达题目的要求长度k后 就放入结果数组中

优化

  • 在这个解法中 有一些递归分支是明显不可能获取到结果的
  • 我们每次递归都会循环尝试 <= n 的所有项去作为start 假设我们要求的数组长度k=3,
  • 最大值n=4而我们以prev = [1], 再去以 n=4为start 作为递归的起点
  • 那么显然是不可能得到结果的，因为n=4的话只剩下4这一项可以拼接, 最多
  • 就拼成[1,4], 不可能满足k=3的条件所以在进入递归之前
  • 就果断的把这些废枝给减掉 这就叫做减枝
let combine = function (n,k){

    let ret = []

    let helper = (start,prev)=>{

        let len = prev.length

        if(len === k){

            ret.push(prev)

            return

        }

        // 还有rest个位置待填补

        let rest = k - prev.length

        for(let i = start;i<=n;i++){

            if(n-i+1<rest){

                continue

            }

            helper(i+1,prev.concat(i))

        }

    }

    helper(1,[])

    return ret

}

相似题型

给定一个可能包含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)
说明: 解题不能包含重复的子集

输入: [1,2,2]

输出:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

剪枝的思路也是和之前相似的 如果循环的时候发现剩余的数字不足以凑成目标长度 就直接剪掉

var subsetsWithDup = function(nums){

    let n = nums.length

    let res = []

    if(!n){

        return res

    }

    nums.sort()

    let used = {}

    let helper = (start,prev,target)=>{ //0,[],2

        if(prev.length === target){

            let key = genKey(prev)

            if(!used[key]){

                res.push(prev)

                used[key] = true

            }

            return

        }

        for(let i = start; i<= n;i++){

            let rest = n - i

            let need = target - prev.length

            if(rest<need){

                continue

            }

            helper(i + 1,prev.concat(nums[i]),target)//1,[1],2     2,[2],2  3,[2],2

                                                    // 2,[1,2],2,  2,[2,2],2

                                                    //1,[1,]3    2,[2],3    3,[3],3

                                                    //2,[1,2],3   3,[2,2],3  

                                                    //3,[1,2,3],3  



        }

    }

  for(let i = 1;i<=n;i++){

      helper(0,[],i) //0,[],3

  }

  return [[],...res]

}

function genKey(arr){

    return arr.join('~')

}

给定一个数组candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合candidates中的每个数字在每个组合中只能使用一次

说明:
所有数字(包含目标数) 都是正整数
解集不能包含重复的组合

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

所求解集为:

[

  [1, 7],

  [1, 2, 5],

  [2, 6],

  [1, 1, 6]

]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,

所求解集为:

[

  [1,2,2],

  [5]

]
  • 与上面思路类似 只不过由于不需要考虑同一个元素重复使用的情况 每次的递归start起点应该是prevStart + 1。
  • 由于数组中可能出现多个相同的元素 他们可能会生成相同的解 比如 [1,1,7]去凑8的时候,可能会用下标为0的1和7去凑8,也可能用下标为1的1和7去凑8
  • 所以在把解放入到数组之前 需要先通过唯一的key去判断这个解是否生成过,但是考虑到[1,2,1,2,7]这种情况去凑10,可能会生成[1,2,7]和[2,1,7]
  • 这样顺序不同但是结果相同的解，这是不符合题目要求的 所以一个简单的方法就是 先把数组排序后再求解 这样就不会出现顺序不同相同的解了
  • 此时只需要做简单的数组拼接即可生成key[1,2,7]->1~2~7
/**

 * @param {number[]}candidates

 * @param {number} target

 * @return {number[][]}

 */

let combinationSum2 = function(candidates,target){

    let res = []

    if(!candidates.length){

        return res

    }

    candidates.sort()

    let used = {}

    let helper = (start,prevSum,prevArr) =>{

        // 由于全是正整数  所以一旦和大于目标值了  直接结束本次递归即可

        if(prevSUm >target){

            return

        }

        // 目标值达成

        if(prevSum === target){

            let key = genkey(prevArr)

            if(!used[key]){

                res.push(prevArr)

                used[key] = true

            }

            return

        }

        for(let i = start;i<candidates.length; i++){

            // 这里还是继续从start本身开始  因为多个重复值是允许的

            let cur = candidates[i]

            let sum = prevSum + cur

            let arr = prevArr.concat(cur)

            helper(i + 1,sum,arr)

        }

    }

    helper(0,0,[])

    return res

}

let genKey = (arr)=> arr.join('~')

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK