Divide file up by values into equal sections
bash, python
Solution
This is not going to be fun for large inputs if you want an optimal solution. You're looking at something that's right in line with some very famous hard problems in CS - Knapsack, Bin Packing and the like. Some simpler, less perfect, solutions might be close enough.
It's not exact but, given your example data-set I managed to get sizes of 214, 197, 194, 199, 205, 182, 195, 192, 199, 199, 206, 208 from a very simple method. It may or may not work with real data.
Method is :
- Sort list by magnitude
- Split list into 3 parts - High, Medium and Low
- Put each member of high in a set.
- Reverse medium and low lists.
- Put them (in reversed order) into the existing sets
Solutions can get significantly more complex as you get closer to optimal partitioning.
Problem
using either bash or python (2.4.x) I have a file - about 100 or so lines in the file and the file is structured like this. ``` aaaaa, 100 aaaab, 75 aaaac, 150 aaaad, 135 aaaae, 144 aaaaf, 12 aaaag, 5 aaaah, 34 aaaai, 11 aaaaj, 43 aaaak, 88 aaaal, 3 baaaa, 25 baaab, 33 baaac, 87 baaad, 111 baaae, 45 baaaf, 99 baaag, 71 baaah, 68 baaai, 168 baaaj, 21 baaak, 11 baaal, 47 caaaa, 59 caaab, 85 caaac, 77 caaad, 33 caaae, 44 caaaf, 16 caaag, 111 caaah, 141 caaai, 87 caaaj, 59 caaak, 89 caaal, 3 ``` and what I want to do is divide it into 12 columns, with each column having roughly the same number of sensors and the sum of each column being close to the same. In other words if I took the above list and split it like this. ``` aaaaa 100 aaaab 75 baaab 33 aaaai 11 baaah 68 baaac 87 aaaak 88 caaaa 59 caaac 77 199 202 197 aaaah 34 baaaf 99 caaad 33 baaad 111 baaal 47 aaaac 150 aaaaj 43 caaae 44 caaaf 16 188 190 199 aaaag 5 aaaaf 12 baaaa 25 aaaad 135 caaai 87 caaag 111 caaaa 59 caaak 89 baaag 71 199 188 207 aaaae 144 baaaj 21 caaaj 59 aaaal 3 baaak 11 caaah 141 baaae 45 baaai 168 caaal 3 192 200 203 ``` it makes 12 columns of equal items and pretty close to even value. I can do it manually but we will end up needing to do this a few times. I'm not even sure where to start with it other than make it into an array, counting the items in the array and do a random split. still stuck on the value leveling though. Any pointers?