arrays - 将数组划分为子数组，以便没有子数组包含重复的元素

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

我想将此数组划分为8个子数组，每个子数组的大小为4，这样子数组就不会有重复的元素。

我可以通过几种方式做到这一点？生成所有排列和单个随机排列的最佳解决方案是什么。子数组的顺序无关紧要。每个子数组中元素的顺序也没有。

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

我的方法是使用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

如您所见，当将所有重复的数字混排在一起后，上述方法将失败，因此，作为hack，我一次又一次重复所有步骤，直到得到结果。

我正在使用JavaScript，但是任何语言的答案都可以，只要可以将其转换为JavaScript。

如果任何人都可以为N个元素和K个组提供通用的解决方案，那也很好。

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

最佳答案

一种选择是先将您的列表分成相同编号的组，然后按长度排序。然后，您可以通过从最长，第二最长，第三最长，第四最长的每个组中选取元素来进行分组。清空子组时，将其删除。

这是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(',')))