Talk:Non-continuous subsequences
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)
- Of course not mind -- badmadevil 09:04, 29 March 2008 (MDT)