CS61A_lab_07

 1 def inc_subseqs(s):
 2     """Assuming that S is a list, return a nested list of all subsequences
 3     of S (a list of lists) for which the elements of the subsequence
 4     are strictly nondecreasing. The subsequences can appear in any order.
 5 
 6     >>> seqs = inc_subseqs([1, 3, 2])
 7     >>> sorted(seqs)
 8     [[], [1], [1, 2], [1, 3], [2], [3]]
 9     >>> inc_subseqs([])
10     [[]]
11     >>> seqs2 = inc_subseqs([1, 1, 2])
12     >>> sorted(seqs2)
13     [[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
14     """
15     def subseq_helper(s, prev):
16         if not s:
17             return [[]]
18         elif s[0] < prev:
19             return subseq_helper(s[1:],prev)
20         else:
21             a = inc_subseqs(s[1:0])
22             b =[ls for ls in a if ls[0]>s[0]]
23             return insert_into_all(s[0], b) +inc_subseqs(s[1:])
24     return subseq_helper(s,-1)