Interesting problem

From: likesh (luka_at_nogo.si)
Date: 03/23/04 

Date: Tue, 23 Mar 2004 13:23:50 +0100

Hello,

I'm trying to figure more appropriate way of solving this interesting
problem.
Problem is:
You have n number of integers (more than 200000) arranged in a sequence. Not
necesseraly all different.
You also have a relation which describes proper sequence of this integers.

Example: you have numbers 1,2,3,4,5,6. Relation is (6<1), (3<2). It means 6
is smaller than 1, 3 is smaller than 2.
It also means that (1<2), (1<3).... ((6<1),(3<2) are just exceptions). If
there is an 'conflict' in sequence with the relation,cost is calculated.

if numb. are arranged in sequence: 1,2,3,4,5,6 this means (6<1) and (3<2)
are in conflict with the relation. Cost of one conflict is calculated as:
(index(high)-index(low)^2. In this case is C= (6-1)^2+(3-2)^2 = 26.

Better solution would be: 1 3 2 6 4 5: Conflicts are: (6<1),(4<6),(5<6).
Cost is C= (4-1)^2+(5-4)^2+(6-4)^2=14.

I have to find an permutation of sequence with the lowest cost in shortest
time. (not necesseraly optimum cost)
I've tried to solve this with checking many (just moving numbers and
calculating cost..) different permutations, but it is very time consuming
algorthm . Although i found out that ordering them from smallest to highest
helps.

Any ideas what kind of procedures i should look into? Any other ideas? Thank
you.

regards

Relevant Pages

  • Re: Factoring - a newbie question
    ... Indeed, most Forths are optimized to minimize this cost, because of the extreme modularity that characterized Forth programming style. ... Factoring this would save 12 words and assuming I can think of a good name for the sequence, the end result should be more readable. ... The issue is often less whether factoring the sequence would save or cost and more whether the factor is a nameable concept. ... Once the word is tested, readability matters only if I have to revisit this particular word - which I think is unlikely, but one never knows. ...
    (comp.lang.forth)
  • Re: Best Match sort sequence
    ... I've tried Internet Explorer, Firefox, Netscape and Safari. ... seller status with good star ratings, high item cost, lots of existing ... Things that will count against you include postal cost being higher ... The sequence is different depending on which browser is used. ...
    (uk.people.consumers.ebay)
  • Re: Best Match sort sequence
    ... results are nothing like each other, which leads me to believe that a seller ... requiring Paypal payment at time of purchase. ... Things that will count against you include postal cost being higher ... The sequence is different depending on which browser is used. ...
    (uk.people.consumers.ebay)
  • Re: Attn: Atheists & Skeptics - Whats wrong with answersingenesis.com?
    ... >> it would take to sequence one set of DNA and change the base pairs to ... >>> John Drayton ... They wanted to get the cost ... By the time the chicken genome was sequenced ...
    (talk.origins)
  • Re: optimizing simple-arrays
    ... Here's another approach where one first builds a sequence of the wrong ... note: doing float to pointer coercion (cost 13), ...
    (comp.lang.lisp)
Loading