--- Raul Miller <[EMAIL PROTECTED]> wrote:
> Background: http://xkcd.com/c287.html
> (That's not really an np-complete problem, near as I can tell.)
>
> Given
> ap=:2.15 2.75 3.35 3.55 4.2 5.8
>
> This will list distinct combinations of ap which total to 15.05:
> ~./:~&.>(#~15.05=+/&>)(#~15.05>:+/\)&.>,{7#<ap
>
> But, that's not very efficient.
>
> A more efficient approach might be
> 15.05 order ap
> where:
>
> order=:4 :0
> min=.<./y
> pos=.,:y
> r=.''
> while.{:$pos=.pos#"1~x>:min++/pos do.
> pos=.(#"1~ <:/@(_2{.])) pos((#"1~#), {:@[EMAIL PROTECTED] ,@# ,:@]) y
> r=.r,<"1|:pos#"1~x=+/pos
> end.
> /:~r
> )
>
> But, maybe that could be more elegant.
>
> Does anyone have any good suggestions?
>
> (Does J's library have any built-ins for addressing this kind
> of problem?)
This is somewhat faster and leaner (x338 and x45) but still NP
ap <@#~(#~ 15.05=ap(+/ . *)~]) (#:i.@(*/))15.05(1+<[EMAIL PROTECTED])ap
+------------------+----------------------------------+
|2.15 3.55 3.55 5.8|2.15 2.15 2.15 2.15 2.15 2.15 2.15|
+------------------+----------------------------------+
____________________________________________________________________________________
Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it's updated for
today's economy) at Yahoo! Games.
http://get.games.yahoo.com/proddesc?gamekey=monopolyherenow
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
