Divide array into sub arrays such that no sub array contains duplicate elements

Question

I have an array of 32 numbers [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]

I want to partition this array into 8 sub arrays each of size 4 such that no sub array has duplicate elements.

In how many ways can I do this? What is most optimal solution to generate all permutations and a single random permutation. Order of sub arrays do not matter. Neither does order of elements inside each sub array.

For my original problem I do not need to generate all permutations. I just have to generate a random permutation every time my program is run.

My approach was to randomly shuffle array using Fisher–Yates algorithm and keep reshuffling it until I get all 8 sub arrays with no duplicate elements. Of course this is not the best approach.

As part of my solution I shuffle array and from this shuffled array start adding elements one by one to sub arrays. If any sub array had a number already then I keep skipping elements from my shuffled array until I reach a number which is not is my sub arrays. This approach fails for some cases.

Pseudocode of what I have tried

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

As you can see above approach fails when after shuffling all duplicate numbers lie at the end so as a hack I repeat all steps again and again till I get result.

I am using JavaScript but answers in any language are welcome as long as they can be converted into JavaScript.

Also it would be great if anyone can provide general solution for N elements and K number of groups.

This is my first question at SO. Feel free to edit/suggest improvements.

Answer 1

An option is to first break up your list into groups of identical numbers, then sort by length. Then you can make groups by taking elements from each group starting at the longest, second-longest, third-longest, fourth-longest. When you empty a subgroup, remove it.

Here's JS implementation:

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