/prog/ - Algorithm

Name: Anonymous 2010-10-21 11:53

There's a n-element array of integers- 1 or 2.
We have to find subsequence which sum equals x.
How to do that ? I have no fucking idea.
Inb4 bruteforce

Name: Anonymous 2010-10-22 4:22

Disregard what I said about subsequences being the same thing as substrings. They apparently are different. Everything else stands.

Name: Anonymous 2010-10-22 4:23

>>40
You are just as retarded as >>36. Please stop posting.

Name: Anonymous 2010-10-22 4:28

>>39

Yeah I'm dumb, I see it now. I was thinking about non-contiguous subsequences at first (because that's what subsequence fucking means, lrn2math) and didn't stop to think about how making it contiguous changes the problem.

Name: Anonymous 2010-10-22 4:32

>>42
Nah

Name: Anonymous 2010-10-22 4:39

>>42
Why are you so mean towards >>40-san? She is right about the following, you know: ^⁶⁶If you just need to find one subset with sum of X, you just pick up to X/2 integers with value of 2 from array, then enough ones for sum to reach X if necessary. This is O(n) in worst case.^⁹⁹

Name: Anonymous 2010-10-22 6:08

>>39
An array of non-negative integers.

Name: Anonymous 2010-10-22 6:30

>>46
Yes, that's crucial, otherwise the problem (2, -1) with target 1 is a counter-example. Or (1, 1, 10, 1, 1, -5) with target 9, to make the problem more obvious.

Also, the fact that the only possible numbers are 1 and 2 is absolutely crucial for the "find a subset" interpretation, otherwise it's NP-complete: http://en.wikipedia.org/wiki/Subset_sum_problem, even with positive integers only.

Name: Anonymous 2010-10-22 7:29

>>47
You just won today's "State the bleedingly obvious in most pompous way" award. Congratulations!

Name: VIPPER 2010-10-22 7:42

>>48
Eat shit and die, Fucking nigger.

Name: Anonymous 2010-10-22 10:11

*African American

Name: Anonymous 2010-10-22 10:36

>>49
Did you know that there exist http://en.wikipedia.org/wiki/Ethiopian_Jews ?

Name: VIPPER 2010-10-22 10:43

>>51
They're not real JEWS, unlike Ashkenazi JEWS. Know your JEWS.

Name: Anonymous 2010-10-27 3:23

If i wish to start on i=0 and j=n-1...
E.g if i know when sum is closer to sum of array than to first element...
How should i modify this >>18 algorithm ?

Name: Anonymous 2010-10-27 5:53

import random



def subsum(n, x):

    while True:

        pick = []

        for i in n:

            if random.randint(0, 1):

                pick.append(i)

        if sum(pick) == x:

            return pick

Best case O(n) algorithm!

Name: Anonymous 2010-10-27 11:33

>>54
HOHOHOHHOHOO U R SO FUNNY HOHOHHOHO

Name: Anonymous 2010-10-27 16:50

>>54

That isn't pointlessly complicated or convoluted, so it's gay.

Name: Anonymous 2010-10-27 17:36

>>38
A-AoRF-kun, we missed you. ;_;

Name: Anonymous 2010-10-27 18:02

It's the 21 matchsticks game, except with n matchsticks.

Name: Anonymous 2013-05-10 21:41

``ＣＤＲ''
``ＣＤＲ''
``ＣＤＲ''

Name: Anonymous 2013-05-10 21:41

``ＣＤＲ''

Name: Anonymous 2013-05-10 21:41

``ＣＤＲ''

Name: Anonymous 2013-05-10 21:41

``ＣＤＲ''

Algorithm

1 Name: Anonymous 2010-10-21 11:53

41 Name: Anonymous 2010-10-22 4:22

42 Name: Anonymous 2010-10-22 4:23

43 Name: Anonymous 2010-10-22 4:28

44 Name: Anonymous 2010-10-22 4:32

45 Name: Anonymous 2010-10-22 4:39

46 Name: Anonymous 2010-10-22 6:08

47 Name: Anonymous 2010-10-22 6:30

48 Name: Anonymous 2010-10-22 7:29

49 Name: VIPPER 2010-10-22 7:42

50 Name: Anonymous 2010-10-22 10:11

51 Name: Anonymous 2010-10-22 10:36

52 Name: VIPPER 2010-10-22 10:43

53 Name: Anonymous 2010-10-27 3:23

54 Name: Anonymous 2010-10-27 5:53

55 Name: Anonymous 2010-10-27 11:33

56 Name: Anonymous 2010-10-27 16:50

57 Name: Anonymous 2010-10-27 17:36

58 Name: Anonymous 2010-10-27 18:02

59 Name: Anonymous 2013-05-10 21:41

60 Name: Anonymous 2013-05-10 21:41

61 Name: Anonymous 2013-05-10 21:41

62 Name: Anonymous 2013-05-10 21:41

Name: Anonymous 2010-10-21 11:53

Name: Anonymous 2010-10-22 4:22

Name: Anonymous 2010-10-22 4:23

Name: Anonymous 2010-10-22 4:28

Name: Anonymous 2010-10-22 4:32

Name: Anonymous 2010-10-22 4:39

Name: Anonymous 2010-10-22 6:08

Name: Anonymous 2010-10-22 6:30

Name: Anonymous 2010-10-22 7:29

Name: VIPPER 2010-10-22 7:42

Name: Anonymous 2010-10-22 10:11

Name: Anonymous 2010-10-22 10:36

Name: VIPPER 2010-10-22 10:43

Name: Anonymous 2010-10-27 3:23

Name: Anonymous 2010-10-27 5:53

Name: Anonymous 2010-10-27 11:33

Name: Anonymous 2010-10-27 16:50

Name: Anonymous 2010-10-27 17:36

Name: Anonymous 2010-10-27 18:02

Name: Anonymous 2013-05-10 21:41

Name: Anonymous 2013-05-10 21:41

Name: Anonymous 2013-05-10 21:41

Name: Anonymous 2013-05-10 21:41