Re: partition of an array

I am not directly acquainted with this problem, but it appears to me that the constraint, “such that |i-j| is 0 or 1,” is merely a formal way of saying, “in half.” Off the top of my head, I think that I can assert that there is only one point in any list where such a constraint would be true in a list with an even number of elements, and only two such points with an odd number.

Therefore, “how is the ‘minimize’ constraint to be satisfied?” It would seem obvious to me that you must alter the order of the elements of the list in some way... a task that could be equally described in terms of “two separate lists.” With such a definition, one might solve the problem by sorting the master-list, then distributing the numbers taken from both the head and the tail of that sorted master-list into the two buckets.

But, again referring to my previous post, I would first “study the literature” to find where someone else has effectively solved the problem for you already. “Heck, it's got to be in CPAN somewhere...”

Replies are listed 'Best First'.
Re^2: partition of an array by ikegami (Patriarch) on Mar 09, 2009 at 19:20 UTC
I think that I can assert that there is only one point in any list where such a constraint would be true in a list with an even number of elements Even without ordering, that's not true. `(1 2 3 4 5 6): (1 2 3) (4 5 6) d=9 (1 2 4) (3 5 6) d=7 (1 2 5) (3 4 6) d=5 (1 2 6) (3 4 5) d=3 (1 3 4) (2 5 6) d=5 (1 3 5) (2 4 6) d=3 (1 3 6) (2 4 5) d=1 <-- (1 4 5) (2 3 6) d=1 <-- solutions (1 4 6) (2 3 5) d=1 <-- (1 5 6) (2 3 4) d=3` [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: partition of an array
by ikegami (Patriarch) on Mar 09, 2009 at 19:20 UTC

I think that I can assert that there is only one point in any list where such a constraint would be true in a list with an even number of elements

Even without ordering, that's not true.

(1 2 3 4 5 6):
  (1 2 3) (4 5 6)  d=9
  (1 2 4) (3 5 6)  d=7
  (1 2 5) (3 4 6)  d=5
  (1 2 6) (3 4 5)  d=3
  (1 3 4) (2 5 6)  d=5
  (1 3 5) (2 4 6)  d=3
  (1 3 6) (2 4 5)  d=1  <--
  (1 4 5) (2 3 6)  d=1  <-- solutions
  (1 4 6) (2 3 5)  d=1  <--
  (1 5 6) (2 3 4)  d=3
[download]

[reply]
[d/l]