1
$\begingroup$

Given an array of integers, how can we generate all the increasing subsequnces of length of 4 ?

Example: given this list

l = [1, 2, 4, 5, 3, 6]

The answer should be :

[1, 2, 3, 6] [1, 2, 4, 5] [1, 2, 4, 6] [1, 2, 5, 6] [1, 4, 5, 6] [2, 4, 5, 6]

I generated this algorithm using python :

def verif(x,temp): work=[] for k in temp: if len(k)<4 : if k[-1] < x : work.append(k+[x]) return work+[[x]] temp=[[1]] for i in range(1,len(l)): print(i) zeta=verif(l[i],temp) for i in zeta: if len(i)==4 : print(i) temp+=zeta zeta=[]

I want to improve my approach , which is very slow for bigger lists unfortunately , is there another algortihm which works faster ?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Is your approach slow, or are there just too many sequences? $\endgroup$ Commented Nov 9, 2020 at 18:54
  • $\begingroup$ For a list of 500 integers , it becomes very slow $\endgroup$ Commented Nov 9, 2020 at 19:08
  • $\begingroup$ $\binom{500}{4} = 2573031125$. That's two and a half billion. $\endgroup$ Commented Nov 9, 2020 at 19:16
  • $\begingroup$ I didn't use combinations $\endgroup$ Commented Nov 9, 2020 at 19:18
  • $\begingroup$ That’s the number of sequences you’re trying to generate. $\endgroup$ Commented Nov 9, 2020 at 19:18

1 Answer 1

Reset to default
1
$\begingroup$

Here is an algorithm to generate all increasing sequences of length $4$ of the numbers $1,\ldots,n$:

for d in {4,...,n}: for c in {3,...,d-1}: for b in {2,...,c-1}: for a in {1,...,b-1}: output a,b,c,d
Improve this answer
$\endgroup$
4
  • $\begingroup$ And what if the sequnces is not sorted ? , this an o(n^4) complexity time , what if we had a 1000 integers list ? $\endgroup$ Commented Nov 9, 2020 at 19:22
  • $\begingroup$ There are $\Theta(n^4)$ sequences. You cannot generate all of them in less than $n^4$ time. $\endgroup$ Commented Nov 9, 2020 at 20:02
  • $\begingroup$ My approach is faster i think in $ O {(n^2)} $ , but i want a linear approach $\endgroup$ Commented Nov 9, 2020 at 20:07
  • $\begingroup$ It is impossible to generate $\Theta(n^4)$ tuples in time $O(n^2)$. Think about it – can you generate 10000 tuples in 100 steps? $\endgroup$ Commented Nov 9, 2020 at 20:16

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.