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

Pages: 1-4041-

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-21 11:54

Not this again.

Name: Anonymous 2010-10-21 11:56

Get the fuck out.

Name: Anonymous 2010-10-21 12:00

What ? What's wrong with you ?

Name: Anonymous 2010-10-21 12:05

inb4 fuck off back to the imageboards

Name: Anonymous 2010-10-21 12:05

Haven't read SICP?
Post your homework to rentacoder.com, maybe someone there will help.
Now leave /prog/ and don't come back until you do every exercise in SICP.

Name: Anonymous 2010-10-21 12:06

There's an O(n2) algorithm, actually.

Name: Anonymous 2010-10-21 12:08

Yeah, it is. But for max input (array of 10^6 elements) its fucking slow

Name: Anonymous 2010-10-21 12:13

>>1
Listen carefully, because I'm not going to say post this twice.
For a n-length sequence of 1's and 2's, create an nxn matrix called m. Define m[x][y] to be the sum of all elements of your input array from A[x] to A[x+y-1], inclusively. Filling this matrix efficiently without recomputing the entire sum is left as an exercise to the reader (now you have two exercises). Please note that entries past x+y>n will be undefined. Now that you've formed your matrix, just search for x in it. The row and column at which you will find it will indicate your solution.

You're welcome, faggot.

Name: >>9 2010-10-21 12:15

There's also a O(n) solution.

Name: Anonymous 2010-10-21 12:19

>>9
create an nxn matrix
>>8
max input (array of 10^6 elements)

Name: >>9,10 2010-10-21 12:20

Start with two indices, i and j, and an integer N representing the sum of all numbers between A[i] and a[j], inclusively.
1) Increment j, add A[j] to N.
2) If N = x, you're done. If N < x, back to the imageboardsstep 1.
3) Subtract A[i] from N. Increment i. Go to 2.

Name: Anonymous 2010-10-21 12:20

>>9 Thanks, but, as I said, there's max of 10^6 elements. I had problems to create one-dimension array of 10^6 elements... It's not a solution.

Name: >>9,10,12 2010-10-21 12:22

Sorry about >>9, it was more of a brain-fart than anything.

Name: Anonymous 2010-10-21 12:23

>>12 It's not a O(n^2) solution ?

Name: Anonymous 2010-10-21 12:24

>>15
Use your brain.

Name: >>12 2010-10-21 12:25

I forgot to say. i, j and N are initialized at zero at the beginning of the algorithm.

Name: >>12 2010-10-21 12:30

Fuck, my brain is dead today. Final version:

Start with two indices, i and j, and an integer N representing the sum of all numbers between A[i] and a[j], inclusively, all initialized to zero.
1) Add A[j] to N, increment j.
2) If N = x, you're done. If N < x, back to the step 1.
3) Subtract A[i] from N. Increment i. Go to step 2.

Name: Anonymous 2010-10-21 12:33

I don't get it. What is the complexity of this solution?

Name: Anonymous 2010-10-21 12:35

>>9
This is a horrible solution.
>>12
This is almost right, but you need an "increment i" step in there somewhere between steps 2 and 3.  And step 3 should not end with "Go to 2."

Name: Anonymous 2010-10-21 12:37

>>20
I'm wrong, "Go to 2" is correct.

>>19
The correct version >>18 is O(n).

Name: >>12 2010-10-21 12:39

WE HELPED HIM!!!

Name: Anonymous 2010-10-21 12:39

>>21
You're implying it isn't correct?

Name: Anonymous 2010-10-21 12:41

>>18
No, this doesn't work.
Let the input be {2 1 2} and let x = 4.  This algorithm will not find a solution.

Name: Anonymous 2010-10-21 12:42

>>24
Because there's no solution.

Name: Anonymous 2010-10-21 12:46

I'm starting to think OP is trolling us.

Name: Anonymous 2010-10-21 12:47

>>25
Oh...  so "subsequence" is not the same as "subset."  Ok.

Name: Anonymous 2010-10-21 12:56

I'm sorry, fuck, i'm not from English language country and it's pretty hard for me to say anything in foreign language, especially in technical speech

Name: Anonymous 2010-10-21 13:03

>>28
OP, if you really did mean to say "subsequence," then 18 is your answer.  If you meant to say "subset," then it's actually slightly easier...  but the solution to that problem is not posted here.

Name: Anonymous 2010-10-21 13:04

>>29
but the solution to that problem is not posted here.
...yet.

Name: Anonymous 2010-10-21 13:09

OP here, It's subsequence i think...
There's no solution in >>24

Name: Anonymous 2010-10-21 13:21

>>31
There's no solution in >>24
Correct, as >>25 said.

Name: VIPPER 2010-10-21 13:32

>>30
...yet.

And it wont be because the solution is JEWS!

Name: Anonymous 2010-10-21 23:56

>>24
>Let the input be {2 1 2} and let x = 4.  This algorithm will not find a solution.

If we're talking about subsequences in the mathematical sense (c.f. http://en.wikipedia.org/wiki/Subsequence) then the solution here is {2 2}. If we're talking about substrings (i.e. contiguous subsequences) then there's no solution.

>>21
The correct version >>18 is O(n).

It can't be O(n). A string of length N has sum [1..N] == (N*(N+1))/2 substrings. Since you have to check O(N^2) substrings to find the solution, a correct algorithm will be at least O(N^2).

Name: Anonymous 2010-10-22 0:07

>>34
What, are you fucking retarded? Discounting the fact you didn't read the problem correctly- do you think every optimization problem can only be solved by exhaustive search too?

Name: Anonymous 2010-10-22 3:19

How am I supposed to know the OP means when he doesn't explain it correctly? He doesn't know the difference between a subsequence and a substring and he never said whether he wanted one solution or all solutions.

>do you think every optimization problem can only be solved by exhaustive search too?

The problem is to find substrings that satisfy a certain condition. How the fuck are you supposed to do that without checking each one? You can return early if you find a solution, but that doesn't change the asymptotic running time. In the worst case there is no solution, which you can only determine by exhaustively searching all O(N^2) substrings and not finding an answer.

Name: Anonymous 2010-10-22 3:32

>>36
Your and idiot.

Name: Anonymous 2010-10-22 3:43

/cygdrive/b $ time sh -c "perl sum.pl 56409 < file.txt"
0..37670

real    0m1.931s
user    0m0.000s
sys     0m0.092s
/cygdrive/b $ perl -e "for(0..1000000){print 1+int(2*rand)}">file.txt
/cygdrive/b $ ls -l file.txt
-rwx------+ 1 Administrators None 1000001 2010-10-22 11:37 file.txt
/cygdrive/b $ time sh -c "perl sum.pl 56409 < file.txt"
0..37484

real    0m1.843s
user    0m0.015s
sys     0m0.047s
/cygdrive/b $ echo 2`cat file.txt` > file.txt
/cygdrive/b $ time sh -c "perl sum.pl 56409 < file.txt"
1..37485

real    0m1.893s
user    0m0.015s
sys     0m0.061s
/cygdrive/b $ cat sum.pl
use strict;

my $target=shift;
my @values=split //,<>;

my $sum=0;

my $left=0;
my $right=0;

while($right<=@values){
        if($sum<$target){
                $sum+=$values[$right];
                $right++;
        } elsif($sum>$target){
                $sum-=$values[$left];
                $left++;
        } else{
                print "$left..$right\n";

                exit;
        }
}

print "No solution\n";
/cygdrive/b $

It would be times faster in C.

Name: Anonymous 2010-10-22 3:45

>>36
OKAY YOU FUQIN ANGERED AN EXPERT PROGRAMMER

The algorithm in >>18 is a O(n) solution to the problem of finding a continuous subsequence of an array of integers, whose sum is equal to a certain integer. The reason why it's O(n) is because you don't recompute the sum of the subsequence A[i:j] every time you move through the array, you just use the previous one.

You don't fuqin believe me? Implement >>18's algorithm and see for yourself, ``faggot''.

Name: Anonymous 2010-10-22 4:07

>>36
Wow you are stupid. He clearly said he wanted one solution ("We have to find subsequence", not "We have to find all subsequences"). Subsequence is the same thing as substring. If you're thinking about subsets, then the problem becomes just [i]trivial[i]. 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 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: 66 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. 99

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

                                                                                                                                            ``ＣＤＲ''                                                                                                                                           
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 -