CODEWITHSUNDEEP
python-3.xlistperformancecombinationssequence
Fernando Ignacio Navajas Ortiz
Fernando Ignacio Navajas Ortiz

Reputation: 1

How to iterate a list, to get combination of all next values

Problem: Obtain the combination of all next values of the array.

Explanation: All the values should be formed by contiguous elements in the array.

Posible solution(not optimal):

l_number= list("24256")
result= []
while l_number:
    n = "" 
    for x in l_number:
        n += x
        result.append(str(n))
    
    l_number.pop(0)
print(result)

The output:

['2', '24', '242', '2425', '24256', '4', '42', '425', '4256', '2', '25', '256', '5', '56', '6']

I got this, but it is not very efficient.

Is there any optimized way to do this?

Upvotes: 0

Views: 75

Answers (1)

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

Since you will be outputting all contiguous sublists, the size of the output will be O(N^2) where N is the length of the list, and time complexity will be at least quadratic no matter what (You could achieve linear space complexity by using a generator). Here is one way to compute all contiguous substrings with a list comprehension:

s = "24256"
n = len(s)
res = [s[i:j] for i in range(n) for j in range(i+1,n+1)]
print(res)
# ['2', '24', '242', '2425', '24256', '4', '42', '425', '4256', '2', '25', '256', '5', '56', '6']

As an aside, it is usually undesirable to build up lists with str += ... since a new copy of str is created on each iteration. One workaround is to create a list of components and call .join once all components have been found.

Upvotes: 1

Related Questions