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

Question

我有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提出的第一个问题。随时编辑/建议改进。

Answer 1

您可以使用位掩码来解决此问题。首先生成所有 17 位数字，其中正好有 4 位设置为 1。这些数字将表示一组中可能的元素，如果设置了数字的第 i 位，则 i+1 是该组的一部分团体。

现在，从这些生成的数字中，您的任务只需重复选择 8 个满足每个元素的频率约束的数字，这可以轻松完成。

如果我找到其他方法，我会回复你。

编辑：或者，您可以按以下方式使用递归：从 8 个数字开始，全部最初设置为 0，首先将 (a[i]-1) 位设置为 1，该位设置为这些数字之一0 并且该数字中的总设置位小于 4。

当您以递归方式到达叶子时，您将获得 8 个代表位掩码的数字，如上所述。您可以使用它们进行分区。

您可以通过最初创建 100 组 8 个数字并从递归返回来使用此方法。一旦使用了所有这 100 个，您可以再次运行此递归以创建双倍于上一步中形成的集合，依此类推。

#include<bits/stdc++.h>

using namespace std;

int num=0;
vector<vector<int> > sets;

void recur(int* arr, vector<int>& masks, int i) {
    if(num == 0)
        return;
    if(i==32){
        vector<int> newSet;
        for(int j=0; j<8; j++)
            newSet.push_back(masks[j]);
        sort(newSet.begin(), newSet.end());
        int flag=0;
        for(int j=0; j<sets.size(); j++){
            flag=1;
            for(int k=0; k<8; k++)
                flag = flag && (newSet[k] == sets[j][k]);
            if(flag) break;
        }
        if(!flag){
            sets.push_back(newSet);
            num--;
        }
        return;
    }
    for(int ii=0; ii<8; ii++) {
        if(__builtin_popcount(masks[ii]) < 4 && (masks[ii] & (1 << (arr[i]-1))) == 0){
            masks[ii] = masks[ii] ^ (1<<(arr[i] - 1));          
            recur(arr, masks, i+1);
            masks[ii] = masks[ii] ^ (1<<(arr[i] - 1));
        }
    }
}

int main() {
    num = 100;
    int num1 = num;
    vector<int> masks;
    for(int i=0; i<8; i++)
        masks.push_back(0);
    int arr[] = {1,2,3,15,16,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,17,17};
    recur(arr, masks, 0);
    for(int j=0; j<num1; j++){
        for(int i=0; i<8; i++){
            //ith group
            printf("%d group : ",i);
            for(int k=0; k<17; k++){
                if(sets[j][i] & (1<<k))
                    printf("%d ",k+1);
            }
            printf("\n");
        }
        printf("\n\n\n======\n\n\n");
    }
    return 0;
}

这是你想要的？