Re: Better Algorithm
- From: Raja Mukherji <rajamukherji@xxxxxxxxx>
- Date: Tue, 19 Aug 2008 01:17:03 -0700 (PDT)
I finally figured out why I wanted to sort out my list...
The line
weights <- weights:sort(:">");
should be
weights <- weights:sort(:"<");
which would actually sort the list in ascending order (like the
comment claimed)
Then if the partial sum exceeds the goal, we can shortcut not only by
not going proceeding to append to the current team, but by not
appending onto the current team less it's last member (since the next
choices for the last member will be heavier).
Thus we can change:
sum2 < goal => (
(dev <- dev > (goal - sum2)) => best
<- sum2;
Next(j, sum2);
);
to
sum2 < goal => (
(dev <- dev > (goal - sum2)) => best
<- sum2;
Next(j, sum2);
) // (
RET;
);
On Aug 14, 12:39 pm, Raja Mukherji <rajamukhe...@xxxxxxxxx> wrote:
Here is another solution you can look at. Unfortunately, it's written
in Wrapl since I haven't used Icon in a while, but I will try to
translate it into Icon and repost it.
It uses a nested function, which I'm deliberately leaving in, in case
someone can translate it into Icon coexpressions. Otherwise, it should
be possible to rewrite it as two separate functions, although "best"
and "dev" will somehow need to be passed in a way they can modified
(perhaps in a record).
Basically I'm iterating through the subsets via weights[i1],
weights[i2], ..., where i1 goes from 1 to n, i2 goes from i1 + 1 to n,
and so on. I'm also short-cutting once (weights[i1] + .. +
weights[ik]) > goal.
Hope this helps in some way,
Raja
MOD Tug;
IMP IO.Terminal USE Out;
DEF Compute(weights) (
-- Sort weights into ascending order
weights <- weights:sort(:">");
VAR total <- 0;
-- Add up the weight to find the total
EVERY total <- total + weights:values;
-- Find our target goal. Note Wrapl has rationals, so this may be a
fraction
VAR goal <- total / 2;
Out:write('Total: {total}, Goal: {goal}\n');
VAR best <- total;
VAR dev <- best - goal;
VAR n <- weights:length;
VAR Next(i, sum) (
-- i is i_k in our subset, sum is the some of weights[i_1] + ... +
weights[i_k]
-- try i_(k+1) = (i_k + 1) .. n
EVERY WITH j <- (i + 1):to(n), sum2 <- sum + weights[j] DO (
-- no need to continue if we've already exceeded the goal
sum2 < goal => (
(dev <- dev > (goal - sum2)) => best <- sum2;
Next(j, sum2);
);
);
);
Next(0, 0);
Out:write('Best: {best}/{total-best}, Deviation: {2 * dev}\n');
);
Compute([100, 125]);
Compute([100, 110, 150, 175, 500]);
Compute([200, 250, 150, 300, 100, 200, 175, 265, 223]);
END Tug.
produces the following output:
Total: 225, Goal: 225/2
Best: 100/125, Deviation: 25
Total: 1035, Goal: 1035/2
Best: 500/535, Deviation: 35
Total: 1863, Goal: 1863/2
Best: 925/938, Deviation: 13
On Aug 14, 5:44 am, Cp200...@xxxxxxxxx wrote:
I am going through a book on programming challenges and decided to try
a few of them in Icon. This one decides how to evenly divide up a
group of people into equal teams for a game of tug of war (based on
weight). I have written it in Euphoria using a binary number increment
as the permutation device (bad, but I am new to this permutations). I
found the permutation algorithm I am using here on the net for Icon.
It runs quite slow as I am brute forcing it. Can anyone speed it up? I
am really just comparing languages.
Thanks! Jeremy
procedure do_permute(l, i,
n)
if i >= n
then
return
l
else
suspend l[i to n] <-> l[i] & do_permute(l, i+1,
n)
end
procedure
permute(l)
suspend do_permute(l, 1,
*l)
end
procedure
compute(args)
local arg, best, total, dev, tmp, cur,
round
every arg := 1 to *args do args[arg] :=
integer(args[arg])
total :=
0
every arg := total +:= !
args
dev := best :=
total
writes("Total: ", total, " Goal: ", total / 2, "
")
every round := permute(args) do
{
cur :=
0
every tmp := !round do
{
cur +:=
tmp
tmp := total - (cur +
cur)
if tmp < 0 then
break
if tmp < dev then
{
dev :=
tmp
best :=
cur
keep :=
round
}
}
}
write("Best: ", best, "/", total-best, " Deviation: ",
dev)
end
procedure
main()
compute(["100",
"125"])
compute(["100", "110", "150", "175",
"500"])
compute(["200", "250", "150", "300", "100", "200", "175", "265",
"223"])
end
.
- Follow-Ups:
- Re: Better Algorithm
- From: Raja Mukherji
- Re: Better Algorithm
- References:
- Better Algorithm
- From: Cp200205
- Re: Better Algorithm
- From: Raja Mukherji
- Better Algorithm
- Prev by Date: Re: Better Algorithm
- Next by Date: Re: Better Algorithm
- Previous by thread: Re: Better Algorithm
- Next by thread: Re: Better Algorithm
- Index(es):
Relevant Pages
|
