js排列组合算法解决方案

最新推荐文章于 2024-01-29 14:55:02 发布

Areocrystal

最新推荐文章于 2024-01-29 14:55:02 发布

阅读量790

点赞数

分类专栏：前端算法

本文链接：https://blog.csdn.net/Areocrystal/article/details/105932147

版权

前端同时被 2 个专栏收录

8 篇文章

订阅专栏

算法

3 篇文章

订阅专栏

本文介绍了如何使用JavaScript解决包含重复数字的排列组合问题。通过递归算法，可以生成给定数组如[1,1,3]或[1,1,2,1,2]的所有可能排列。详细代码和验证输出展示了算法的正确性。" 113482318,9096836,JS基础教程：从入门到精通,"['JavaScript', '前端开发']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

之前文章中谈过排列组合算法，主要事递归，代码如下

const arrangeCombination = arr => {
    const res = [], len = arr.length, inner = ary => {
        for (let i = 0; i < len; i++) {
            let notHas = !ary.includes(arr[i]), tmp = [...ary, arr[i]];
            if (ary.length === len - 1) {
                notHas && res.push(tmp)
                continue
            }
            notHas && inner(tmp);
        }
    }
    inner([]);
    return res;
}

例如输入[1,2,3],

输出：[[ 1, 2, 3 ],[ 1, 3, 2 ],[ 2, 1, 3 ],[ 2, 3, 1 ],[ 3, 1, 2 ],[ 3, 2, 1 ]]。

不过只能解决无重复数的排序问题。

这几天稍作研究，尝试解决出了无重复数的排序，下面直接上代码

const arrangeCombinationRepeat = arr => {
    const res = [], len = arr.length,
        //保证两个数组中所有数所出现次数一致
        arrCompare = (a, b) => {
            const c = arr => arr.reduce((pre, cur) => (pre[cur] ? pre[cur]++ : (pre[cur] = 1), pre), {}), oa = c(a),
                ob = c(b)
            for (let i in oa) {
                if (oa[i] !== ob[i]) {
                    return false
                }
            }
            return true
        },
        inner = ary => {
            for (let i = 0; i < len; i++) {
                let tmp = [...ary, arr[i]];
                if (ary.length === len - 1) {
                    arrCompare(arr, tmp) && res.every(arr => JSON.stringify(arr) !== JSON.stringify(tmp)) && res.push(tmp);
                    continue
                }
                inner(tmp);
            }
        };
    inner([]);
    return res;
}

验证输入：[1,1,3]

输出：[ [ 1, 1, 3 ], [ 1, 3, 1 ], [ 3, 1, 1 ] ]。

输入：[1,1,2,1,2]

输出：[
[ 1, 1, 1, 2, 2 ],
[ 1, 1, 2, 1, 2 ],
[ 1, 1, 2, 2, 1 ],
[ 1, 2, 1, 1, 2 ],
[ 1, 2, 1, 2, 1 ],
[ 1, 2, 2, 1, 1 ],
[ 2, 1, 1, 1, 2 ],
[ 2, 1, 1, 2, 1 ],
[ 2, 1, 2, 1, 1 ],
[ 2, 2, 1, 1, 1 ]
]。