How to improve Increasing Subsequences algorithm to incorporate un-sorted array? -

i have been working on solving increasing subsequence problem. algorithm came solves sorted arrays. writing code in python 3.5. problem hosted on leetcode.

in increasing subsequence problem, given integer array, task find different possible increasing subsequences of given array, , length of increasing subsequence should @ least 2.

example:

input- [4,6,7,7]

output - [[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7],[6,7,7],[7,7],[4,7,7]]

here working code solving question:

array = [4,6,7,7]  def incrsubseq(array): #only works sorted arrays.     res = [[]]     ans = []     num in array:         res += [item + [num] item in res if (item+[num] not in res)]     values in res:         if len(values)>1:             ans = ans + [values]     print(ans) incrsubseq(array) 

how code work?

1. it starts initializing result variable res (a list of lists) initialized empty list.
2. then iterate through given integer array array in sorted order, adding each element list, finding subsets of can formed. if statement inside list comprehension filters out items duplicate , keeping 1 copy of list.
3. then filter array has length greater 1.

thus, solving problem.

now, missing here way solve unsorted array. far understanding goes need put check in manner when trying add element res should greater or equal item before it.

res += [item + [num] item in res if (item+[num] not in res) , (item <= num)] gives in empty lists.

any suggestions on improving code?

your idea correct! check if last element in item smaller previous (maybe allow equal, depending on how 1 defined increasing).

so add check item[-1] <= num (with -1 last element of array in python).

now there 1 more problem. item empty , error. want <= check, if there @ least 1 element in item. below fancy solution using short circuiting of boolean operations (len(item) == 0 or item[-1] <= num) true when either there no element (then second check not performed), or there @ least 1 element in item , check if smaller or equal.

array = [4,6,3,7]  def incrsubseq(array): # works sorted arrays :)     res = [[]]      num in array:         res += [item + [num] item in res if (item + [num] not in res                                                   , (len(item) == 0 or item[-1] <= num))]      return [values values in res if len(values) > 1]  print(incrsubseq(array)) 

---

short circuiting means boolean expression evaluated until final value can determined. example false , 1/0 not raise exception because and false if any of 2 arguments false. when evaluation goes left right not calculate 1/0.

a bit more verbously inner part of above algorithm can written as:

for num in array:     item in res:         if item + [num] not in res:             if len(item) == 0:                 # item empty.                 res += [num]             else:                 # item not empty check last element.                 if item[-1] <= num:                     res += item + [num]                 else:                     # got increasing here. not add.                     pass 

---

the complexity of algorithm can calculated followed. suppose worst case input of [1, 2, ..., n]. in each step number of resulting subsequences doubled, resulting in o(2^n) subsequences , output size of o(n * 2^n). every algorithm take @ least long (if interested in outputting every sequence -- if want generate on fly aka. iterator , lazy evaluation style of functional languages not matter).

this algorithms takes longer though. main work have each subsequence in output check if duplicate doing naive item + [num] not in res. comparison of 2 lists of length m takes o(m) worst case. , considering last num takes more half of total runtime use approximation here. means check of last 2^(n-1) created subsequences takes o(2^(n-1) * 2^(n-1) * n) = o(n * 4^n) because check every new sequence every old. prefix tree result datastructure reduced o(2^n) checking if new subsequence valid requires o(1). traversing tree write down solutions requires again o(2^n * n).

sidenote: if functional programming in python check out syntax_sugar_python,