将数组划分为子数组，使子数组不包含重复元素

Question

我有一个由32个数字组成的数组[1,2,3,4,4,4,4,4,5,5,5,5,5,5,5,5,6,6,7,7,7,7,8,9,10,10,11,9,12,13,13,14,14,15,16,17,17]

对于我最初的问题，我不需要生成所有的排列。我只需要在每次运行我的程序时生成一个随机排列。

我的方法是使用Fisher-Yates算法随机洗牌数组，并不断重新洗牌，直到我得到所有8个子数组，没有重复的元素。当然，这不是最好的方法。

作为解决方案的一部分，我洗牌数组，从这个洗牌数组开始一个接一个地向子数组添加元素。如果任何子数组已经有一个数字，那么我会继续跳过我的洗牌数组中的元素，直到我达到一个数字，而这个数字不是我的子数组。这种方法在某些情况下是失败的。

let shuffledArray = shuffle(originalArray);
let subArrays = [];
for (let i = 0; i < 8; i++) {
    subArrays[i] = [];
    for (let j = 0; j < 32; j++) {
        if (!subArrays[i].contains(shuffledArray[j]) && !shuffledArray[j].used) {
            subArrays[i].push(shuffledArray[j])
            shuffledArray[j].used = true;
        }
        if (subArrays[i].length == 4) {
            break;
        }
    }
}

 if subArrays has any sub array such that it has duplicate elements then repeat above steps
 else we have generated a random permutation

如果有人能给出N个元素和K个群的通解，那就太好了。

这是我在SO的第一个问题。请随时编辑/提出改进建议。

Answer 1

一个选择是首先将列表分成相同的数字组，然后按长度排序。然后，您可以通过从最长、第二长、第三长、第四长的每个组中提取元素来创建组。清空子组时，将其移除。

以下是JS实现：

function partition(arr, N){
    // group items together and sort by length
    // groups will be [[5, 5, 5, 5, 5], [4, 4, 4, 4], ...]

    let groups = Object.values(l.reduce((obj, n) =>{
        (obj[n] || (obj[n] = [])).push(n)
        return obj
    }, {})).sort((a,b) => b.length - a.length)

    let res = []
    while(groups.length >= N){
        let group = []
        let i = 0
        while (group.length < N){
           group.push(groups[i].pop())
           if (groups[i].length < 1) groups.splice(i, 1)
           else i++
        }
        res.push(group)
    }
    return res
}
let l = [1,2,3,4,4,4,4,5,5,5,5,5,6,6,7,7,7,7,8,9,10,10,11,12,13,13,14,14,15,16,17,17]


console.log(partition(l, 4).map(arr => arr.join(',')))

// with 5
console.log(partition(l, 5).map(arr => arr.join(',')))