Talk:Non-continuous subsequences: Difference between revisions
Content added Content deleted
m (add a note) |
No edit summary |
||
Line 13: | Line 13: | ||
I've not got a formal training in computer science, please try to understand casually, thank you. -- [[User:Badmadevil|badmadevil]] 05:05, 29 March 2008 (MDT) |
I've not got a formal training in computer science, please try to understand casually, thank you. -- [[User:Badmadevil|badmadevil]] 05:05, 29 March 2008 (MDT) |
||
: Looks good. I understood the "beside first and last element" incorrectly, my fault. If you don't mind, I've changed the wording of your explanation in the example a bit. --[[User:Dirkt|Dirkt]] 07:31, 29 March 2008 (MDT) |
Revision as of 13:31, 29 March 2008
Question: How does D's algorithm make sure not calculating the same subsequence twice?
This is the algorithm description in D session:
- from the original sequence, select some continuous subsequences of length >= 3,
- from each continuous subsequences in (1), remove some in-between elements beside first and last element,
- each subsequences some elements removed in (2) is a non-continuous subsequences.
Explanation:
- I assume the order in task description mean index order(or position of elements in a sequence/list), so that values of element is not relevant to order, not need to be sorted, nor need to be comparable <Just read the remark in the bottom of D session. This part of comment is not necessary, but may keep as a record of discussion -- badmadevil 05:24, 29 March 2008 (MDT) >;
- each subsequence in (1), or contseq in D's example code, is uniquely determined by its head element index and tail element index;
- when removing elements from contseq in (2), the elements indexed by head and tail is not touched, so each non-continuous sequence produced by this contseq will not overlap with other non-continuous sequence produced by another contseq, since they must have different pair of head/tail indexs;
- within those non-continuous sequence produced by the same contseq, if they have been taken out different numbers of elements, they are of course different non-continuous sequences, because they have different number of elements ;
- for those non-continuous sequence produced by taken out same number of elements from the same contseq, the uniqueness of non-continuous sequences is supported by uniqueness of set of index of elements to be removed ( removeIndexs in D's code) produced by Combi iterator.
I've not got a formal training in computer science, please try to understand casually, thank you. -- badmadevil 05:05, 29 March 2008 (MDT)
- Looks good. I understood the "beside first and last element" incorrectly, my fault. If you don't mind, I've changed the wording of your explanation in the example a bit. --Dirkt 07:31, 29 March 2008 (MDT)