loop and process items in list, reloop until all items have been processed

Question

I've found similar but not identical questions 742371 and 4081217 with great answers, but haven't come to a solution to my problem.

I'm trying to process items in a list in place while it's being looped over, and re-loop over what's remaining in the list if it has not met a conditional. The conditional will eventually be met as True for all items in the list, but not necessarily on a "known" iteration. It reminds me of building a tree to some degree, as certain items in the list must be processed before others, but the others may be looped over beforehand.

My first instinct is to create a recursive function and edit a slice copy of the list. However I'm having little luck ~

I won't initially know how many passes it will take, but it can never be more passes than elements in the list... just by the nature of at least one element will always meet the conditional as True

Ideally ... the result would be something like the following

 # initial list
myList = ['it1', 'test', 'blah', 10]
newList = []

# first pass
newList = ['test']

# 2nd pass
newList = ['test', 'blah', 10]

# 3rd pass 
newList = ['test', 'blah', 10, 'it1']

score 4 · Accepted Answer · answered Aug 30 '11 at 04:14

4

current = ['it1', 'test', 'blah', 10]
results = []
while current:
    remaining = []
    for item in current:
        (results if meets_conditional(item) else remaining).append(item)
    current = remaining

answered Aug 30 '11 at 04:14

Karl Knechtel

62,466
11
102
153

seems to go into an infinite loop ~ def meets_conditional(item): if type(item) is str: return True; else: return False – T Carrasco Aug 30 '11 at 05:31
You said "The conditional will eventually be met as True for all items in the list" -- if that's the case, this method will work. Since `10` is never a `str`, your example doesn't meet that criteria. Also, use `isinstance` not `type` in general. – agf Aug 30 '11 at 06:12
only if you care about its inheritance, in this case i do not ~ however, good call on the eventually True. Karl solved it. Cheers – T Carrasco Aug 30 '11 at 06:26

Gerrat · Answer 2 · 2011-08-30T04:04:24.117

1

How about something like this (just made up a silly condition so I could test it):

import random

myList = ['it1', 'test', 'blah', 10]
newList = []

def someCondition(var):
    return random.randrange(0,2) == 0

def test():

    while len(myList) > 0:
        pos = 0
        while pos < len(myList):
            if someCondition(myList[pos]):  # with someCondition being a function here
                newList.append(myList.pop(pos))
            else:
                pos += 1

if __name__ == '__main__':
    test()
    print(myList)
    print(newList)

[Result:]

[]
['it1', 10, 'blah', 'test']

edited Aug 30 '11 at 04:04

answered Aug 30 '11 at 03:52

Gerrat

28,863
9
73
101

Each `pop` is O(n) so you can get better time complexity with something like @Karl's method. – agf Aug 30 '11 at 06:10

score 0 · Answer 3 · answered Aug 30 '11 at 03:47

A brute force approach would be to create a temporary list of booleans the same size as your original list initialized to False everywhere.

In each pass, whenever the item at index i of the original list meets the condition, update the value in the temporary array at index i with False.

In each subsequent pass, look only at the values where the corresponding index is False. Stop when all values have become True.

Grr, come to think of it, keep a set of indexes that have met the condition. Yes, sets are better than arrays of booleans.

loop and process items in list, reloop until all items have been processed

3 Answers3