![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Seeking a program or algorithm.
Aug. 11th, 2018 10:59 amA question for computer people: I have need of a program to optimize something, and its general form seems like a program that must have been written a thousand times already, so I'd like to save some time by not doing it all from scratch. Any leads (on existing programs or well regarded algorithms) would be appreciated. (Note that while I can program, I am not experienced in any modern environments. I wouldn't even know if what I'm looking for is a standard library function.)
The program needs to organize a set of roughly sixty elements into five groups. Each pair of elements has a numerical rating of the desirability of their being in the same group. Find the grouping that maximizes total desirability. Complicating matters is that there are three types of elements: Each group is to have one element of the first type, three of the second type, and eight of the third type.
Since there's no practical difference between group 1 and group 5, I could do an end-run around that requirement by running a smaller version of the program, um, 16!/6^5 = 168,168,000 times, once for each possible grouping of the first and second types of elements. Okay, maybe not.
I don't even know whether this is np-hard. My first visualization of a non-brute-force solution strikes me as way too complicated to bother coding. Total permutations = 40!/8!^5 * 16!/6^5 = about 1.3 * 10^33, so a brute force program finishing in a day would judge about 1.5 * 10^28 permutations per second. My computer isn't quite that fast.
The program needs to organize a set of roughly sixty elements into five groups. Each pair of elements has a numerical rating of the desirability of their being in the same group. Find the grouping that maximizes total desirability. Complicating matters is that there are three types of elements: Each group is to have one element of the first type, three of the second type, and eight of the third type.
Since there's no practical difference between group 1 and group 5, I could do an end-run around that requirement by running a smaller version of the program, um, 16!/6^5 = 168,168,000 times, once for each possible grouping of the first and second types of elements. Okay, maybe not.
I don't even know whether this is np-hard. My first visualization of a non-brute-force solution strikes me as way too complicated to bother coding. Total permutations = 40!/8!^5 * 16!/6^5 = about 1.3 * 10^33, so a brute force program finishing in a day would judge about 1.5 * 10^28 permutations per second. My computer isn't quite that fast.
