CODEWITHSUNDEEP
algorithmpermutationmathematical-optimization
MightyPork
MightyPork

Reputation: 18861

Finding permutations for balanced distribution of values in lists

Sorry for the bad title, but I don't know how to call this.

I have K lists, N elements in each, for example:

[8, 5, 6]
[4, 3, 2]
[6, 5, 0]

and I want to find such a permutation of the lists' elements, so that the sum of elements in first column, second column etc are as close to each other as possible (so the distribution is "fair").

In my example that would be (probably):

      [8,  5,  6]
      [4,  2,  3] -- the lists contain the same values
      [0,  6,  5]    just in different order
sums: 12, 13, 14

Is there some more elegant way than finding all the permutations for each list, and brute-force finding the "ideal" combination of them?

I'm not asking for code, just give me a hint how to do it, if you know. Thanks!

ps. the lists can be quite large, and more of them - think ~20x~20 max.

Upvotes: 3

Views: 162

Answers (1)

slaur4
slaur4

Reputation: 504

If you can accept an approximation, I would do it iteratively :

  • Sort matrix lines by descending weight (sum of line elements). Edit : Sorting first by max element in line could be better.
  • Each time you are going to add a new line to your result matrix, put smaller elements into higher columns.
  • Order lines of your result matrix back to their initial state (if you have to).

It works with your example, but will obviously not be always perfect.

Here is an example (javascript)

Upvotes: 2

Related Questions