Re^2: "Divide" challenge

Brute forcing is not quite as straight forward as one might think :-)

The solution above is working a lot harder than is really necessary, even for a brute force solution. If I understand the problem correctly, we are trying to minimize the data exchanged between the groups. Therefore what matters is the sum of data exchanged between the two groups, not the internal composition of each group.

This lets us significantly reduce the potential solution space. The combination generator above generates every single permutation of 4 elements drawn from 8, not just every single combination. For example, this is the list of combinations produced by gen_set([0..3],[],2, \@combos);. There are 12 items, but if we disregard order only 6 would count.

<0 1> <0 2> <0 3> <1 0> <1 2> <1 3>
<2 0> <2 1> <2 3> <3 0> <3 1> <3 2>
[download]

In actual fact, though we need only half of the combinations, even after ignoring order. This is because our second bag is always the complement of our first bag. Since sums are commutative, trying out the division (bag 1, complement of bag 1) is going to result in the exact same data flow sum as the division (complement of bag 1, bag 1)

Best, beth

Comment on Re^2: "Divide" challenge Select or Download Code

Replies are listed 'Best First'.
Re^3: "Divide" challenge by bellaire (Hermit) on Mar 10, 2009 at 18:11 UTC
Thanks, beth, I'll ++ tomorrow when I have more votes. :) This was definitely working harder than necessary to obtain a solution, and no attempt was made at optimization. However, even doing things the "dumb" way, the whole operation still runs in the blink of an eye, which detracts from the OP's assertion that this would be a difficult problem to brute force, in principle.	[reply]
Re^3: "Divide" challenge by repellent (Priest) on Mar 12, 2009 at 21:53 UTC
Hmmm... I wonder why moritz mentioned 8! / (4! * 2!) == 840 possibilities, when we only need to traverse 8! / 2 * (4! * 4!) == 35 possibilities at minimum. Am I missing something? Read more... (2 kB) Output: `Lowest cost (803) groups are: $VAR1 = [ 0, 1, 4, 6 ]; $VAR2 = [ 2, 3, 5, 7 ];` [download]	[reply] [d/l] [select]