Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Fastest algorithm Discussion

Name: Anonymous 2008-04-04 16:43

Anyway just for fun and learning I have been messing with algorithms in my head.  Here is the problem:  There is a set of numbers N, Is there a subset of exactly two of them which equal a number Z. 

So for instance, 1,4,6,125,185 and the sum 129.  Would return true. 

What is the fastest exact way to do this for arbitrarily large numbers?

I know one method is to take the largest and smallest (1,129) and move each one up or down depending on < or >.  This method takes O(N) time.

What are the faster algs for this?

Name: Anonymous 2008-04-04 16:50

>>1
Give it up, it's NP-complete.

Name: Anonymous 2008-04-04 16:55

Big O notation is for people with big anuses.

Name: Anonymous 2008-04-04 17:04

>>2
No it's not

It is a special case of an NP-complete problem.

The NP-Complete case assumes any possible combination. L2READ

Name: Anonymous 2008-04-04 17:18

>>1
Though, that method requires the set to be sorted first.

Name: Anonymous 2008-04-04 17:21

>>3
Don't worry, I don't get it too.

Name: Anonymous 2008-04-04 17:22

>>4
Give it up, YAHT YHL HAND.

Name: Anonymous 2008-04-04 17:28

Here is a fast solution that requires cons:


(define (algorithm l sum)
 (cons sum (algorithm l sum)))

Name: Anonymous 2008-04-05 1:49

>>8
How would I implement this in QBasic?

Name: Anonymous 2008-04-05 13:51

>>9
Troll?

Name: David M. Gay 2008-04-05 15:02

static Bigint *
Balloc
#ifdef KR_headers
    (k) int k;
#else
    (int k)
#endif
{
    int x;
    Bigint *rv;
#ifndef Omit_Private_Memory
    unsigned int len;
#endif

    ACQUIRE_DTOA_LOCK(0);
    if (rv = freelist[k]) {
        freelist[k] = rv->next;
        }
    else {
        x = 1 << k;
#ifdef Omit_Private_Memory
        rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
#else
        len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
            /sizeof(double);
        if (pmem_next - private_mem + len <= PRIVATE_mem) {
            rv = (Bigint*)pmem_next;
            pmem_next += len;
            }
        else
            rv = (Bigint*)MALLOC(len*sizeof(double));
#endif
        rv->k = k;
        rv->maxwds = x;
        }
    FREE_DTOA_LOCK(0);
    rv->sign = rv->wds = 0;
    return rv;
    }

Name: Anonymous 2008-04-05 16:39

My algorithm is O(0).

Name: Anonymous 2008-04-06 0:55

>>12

1?

Name: Anonymous 2008-04-06 1:03

Use the space ship operator
<=>
if less then, equal too, or greater then.

Name: Anonymous 2008-04-06 1:06

With the spaceship operator, you too can write algorithms that run in O(n) time.

Name: Anonymous 2008-04-06 4:24

take 3 (enumFrom '<')

Name: Anonymous 2008-04-06 5:08

>>14
I find it pretty surpising that you can actually write compilable programs, if that turns out to be the case.

Name: Anonymous 2008-04-06 7:04

>>16
<(+

Name: Anonymous 2008-04-06 8:47

>>18

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude> take 3 (enumFrom '<')
"<=>"

Name: Anonymous 2008-04-06 9:56

>>19
enumFrom is certainly an interesting construct. Hooray lazy evaluation.

Name: Anonymous 2008-04-06 10:03

>>19
You and your newfangled ass-key.

Name: Anonymous 2008-04-06 10:08

>>20,21 are irrelevant to the fact that >>18 was wrong.

Name: Anonymous 2008-04-06 10:22

>>24-
Faggots.

Name: Anonymous 2008-04-06 10:27

>>22 is incognizant to the fact that >>18 made an EBCDIC joke.

Actually Haskell uses Unicode which is compatible with ASCII, but jokes don't always have to be technically correct

Name: Anonymous 2008-04-06 10:27

>>22 come back to us when you have at least 10 years of experience with differend flavours of IBM mainframes.

Name: Anonymous 2008-04-06 10:31

>>25
That's such a  long time, I doubt 4chan will be alive then. But I can write you an email.

Name: Anonymous 2008-04-07 11:19

>>24
UTF-8 you mean?

Name: Anonymous 2009-03-06 6:51


Language of choice is   cat and echo.

Name: Anonymous 2011-02-03 4:05

Name: Anonymous 2011-02-04 12:04

Name: Sgt.Kabukiman 2012-05-21 13:57

All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
 All work and no play makes Jack a dull boy
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -