Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Really need help..

Subject: Really need help..

From: fani vafeiadou

Date: 5 Feb, 2009 22:10:10

Message: 1 of 9

hello everyone! im new to MAtlab and facing several problems..
i have the following task:
we should write a program, which computes the longest increasing subsequence in a given sequence, e.g.
Initial sequence is:
     6 1 7 4 9 5 8 3 10 2

Answer is:
     1 4 5 8 10
  or

Initial sequence is:
     8 9 2 10 3 7 4 1 5 6

All the possible longest increasing subsequences are:
     2 3 4 5 6

could anyone help?

Subject: Really need help..

From: Matt Fig

Date: 6 Feb, 2009 01:02:02

Message: 2 of 9

I have two solutions, neither of which I am very happy with. First let me ask, are the values in the sequences unique? For example, are they of the form

randperm(N)

Your example seems to indicate that they are.
Second, what have you done so far? What are your thoughts on approaching this problem?




MBV%ML_Ay_TEfBAAPYTOOf_LOEAU PAAOTH-GUCCI_NKE___9HOIHm_OEAN

Subject: Really need help..

From: Roger Stafford

Date: 6 Feb, 2009 03:33:02

Message: 3 of 9

fani vafeiadou <fani_vafeiadou@hotmail.com> wrote in message <3676195.1233871866511.JavaMail.jakarta@nitrogen.mathforum.org>...
>.......
> we should write a program, which computes the longest increasing subsequence in a given sequence,
> .......

  This is not giving you the solution to your problem, Fani, but it reminds me very much of a examination question that is said to have been given to pupils applying for admission to Moscow University many years ago. I cannot resist the temptation of describing it.

  Prove that in any arbitrary permutation of the integers from 1 to 101, there will always exist a subsequence which is either all ascending or all descending and which contains at least 11 of the integers.

  Apparently at M.U. they were determined that if they had any very bright applicants, these would definitely not be overlooked.

  If I remember correctly, the proof of the above assertion contains aspects of a recursive procedure that could be used to solve your particular problem. I won't bother you with the details, since there may be more computer-efficient ways of doing it.

Roger Stafford

Subject: Really need help..

From: fani vafeiadou

Date: 6 Feb, 2009 10:58:29

Message: 4 of 9

well its not such a preclass assignment, its just a homework on marketing.
i face problems understanding MAtlab, and thats where i need help.
i ve done already the following
efunction best_seq=funseq;
N=10;
initial_seq=randperm(N);
disp('Initial sequence is:');
disp(initial_seq);
global finseq maxprofit curseq;
maxprofit=0;
finseq=[];
findseq2(initial_seq);
disp('All the possible longest increasing subsequences are:');
disp(finseq);

Subject: Really need help..

From: Matt Fig

Date: 6 Feb, 2009 16:08:01

Message: 5 of 9

What is in findseq2?





&jgbgknna9ds~``D-d~`~un`~`Xad`k~L?s~g~tnst`&xfohlnl~homdbmn

Subject: Really need help..

From: fani vafeiadou

Date: 6 Feb, 2009 18:51:04

Message: 6 of 9

its finseq.

Subject: Really need help..

From: Roger Stafford

Date: 6 Feb, 2009 21:58:02

Message: 7 of 9

fani vafeiadou <fani_vafeiadou@hotmail.com> wrote in message <3676195.1233871866511.JavaMail.jakarta@nitrogen.mathforum.org>...
> .......
> i have the following task:
> we should write a program, which computes the longest increasing subsequence in a given sequence,
> ......

  Because it seems a little unfair to assign this kind of homework problem to students in marketing, I am willing to give you some limited assistance as to its solution, Fani.

  The key to solving it in an efficient manner is this. (I am assuming here that all elements are distinct; if not, the needed adjustment is easily made.) As a first step, start at the first element of the given initial sequence and collect all elements which are the smallest element up to that point. That is, in your example of [8 9 2 10 3 7 4 1 5 6] it would be [8 2 1]; each of these is the smallest element encountered up to that point in the original sequence. Another way of saying this is that each of the other elements not among these three have the property that there exists an element in [8 2 1] which is both earlier and smaller. It requires only a single pass through the initial sequence to find this subsequence.

  Now remove these elements from the initial sequence. In the example it would leave behind only the seven elements [9 10 3 7 4 5 6]. Then repeat this process on this smaller sequence, arriving at [9 3], and leaving [10 7 4 5 6]. At the third such step you get [10 7 4] leaving [5 6]. At the fourth step you get just [5], leaving [6]. At the fifth step you get just [6] leaving an empty set. Now you have successfully partitioned the original example sequence into a set of six disjoint subsequences:

 [8 2 1], [9 3], [10 7 4], [5], and [6]

  At this point you are entitled to conclude both that there must exist an ascending subsequence with 5 elements and that that is the longest such sequence possible.

  As to finding such a longest subsequence, recall that all the elements outside of [8 2 1] have the property that an element exists in [8 2 1] which is earlier and smaller, and in particular this applies to elements of the next set [9 3]. This also holds true for all pairs of consecutive partitioned subsequences. For each element of a partitioned sequence there exists an element somewhere in the previous partition that is earlier and smaller. Starting with 6 and working backwards, the previous 5 must be chosen. From 5 only the 4 in the previous set [10 7 4] is possible. Continuing this, you arrive at the subsequence [2 3 4 5 6] which in this case is the only one possible. In general there may be a number of choices along the way.

  For each step in this backwards process at an element selected in that partition, there will have to be a scan searching for an earlier and smaller element in the previous partition set. You know there has to be at least one to be found at each step. That means a scan for each partitioned set.

  All told, you are faced with twice the number of scans as there are partitions, once for the forward process and once for the backwards process.

  As you will have guessed by now, I have left all the details of implementing such a procedure to you. It will not be a trivial thing to write, but for long initial sequences it is unlikely in my opinion that any other basic kind of algorithm would be able to match one along these lines for efficiency.

Roger Stafford

Subject: Really need help..

From: Matt Fig

Date: 7 Feb, 2009 00:12:01

Message: 8 of 9

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message

Hello Roger. I have worked out several different solutions for this problem, some of which I like more than others. Do you have an implementation of the algorithm you describe above? I would be curious as to how it compares with what I worked out. If you are up for it, could you email me so I can send what I have to you? The email I use here is valid (and I only use it for when I know it will get spammed like here in public). I will not release your email, if you choose to do so. Thanks.




R84AR,<R@4;5R?B<BY4IG4488w4BB:Gl8;?R56@C`HGr>RB;A6 RYLRBH4C

Subject: Really need help..

From: Zhelyazko

Date: 11 Feb, 2009 03:52:01

Message: 9 of 9

Look at Patience Sorting
http://www.perlmonks.org/?node_id=547199

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us