Python: Convert a depth first search to a breadth first search for all combinations of a list

Question

I have a simple recursive function that provides a depth first search of each possible combination of a list of options:

def twoCharacters_dfs(options, used):
    for i in range(len(options)):
        used.append(options.pop(0))
        print("used=", used)
        twoCharacters_dfs(options, used)
    if len(used) == 0:
        return
    options.append(used.pop())

twoCharacters_dfs(['q', 'w', 'e', 'r'], [])

The ouput (shortened due to length) looks as follows:

used= ['q']
used= ['q', 'w']
used= ['q', 'w', 'e']
used= ['q', 'w', 'e', 'r']
used= ['q', 'w', 'r']
used= ['q', 'w', 'r', 'e']
used= ['q', 'e']
used= ['q', 'e', 'r']
used= ['q', 'e', 'r', 'w']
used= ['q', 'e', 'w']
used= ['q', 'e', 'w', 'r']
....
used= ['w']
....
used= ['e']
....
used= ['r']
....

And that is all well and good and works how i want it. But I am interested in converting this from depth first to breadth first so the output looks more like:

used= ['q']
used= ['w']
used= ['e']
used= ['r']
used= ['q', 'w']
used= ['q', 'e']
used= ['q', 'r']
used= ['w', 'q']
used= ['w', 'e']
used= ['w', 'r']
....

I have been somewhat able (only a hard-coded fixed length list) to do it iteratively, but desire a recursive solution so it can work for any length of options. I am also purposely avoiding python libraries that provide the functionality i seek because i would like to understand how things work and build my own stuff as a learning exercise.

I feel like there is a simple solution, but i am having trouble conceptualizing the breadth first algorithm into my code.

UPDATE

Before attempting a recursive BFS solution i wanted to create an iterative BFS solution as it appears to be easier to implement. As it turns out, i am also having trouble doing that.

def twoCharacters_bfs_iterative(options, used):
    for option in options:
        print("using option = ", option)

    for option1 in options:
        list2 = options[:]
        list2.remove(option1)
        for option2 in list2:
            print("using option = ", option1, option2)

    for option1 in options:
        list2 = options[:]
        list2.remove(option1)
        for option2 in list2:
            list3 = list2[:]
            list3.remove(option2)
            for option3 in list3:
                print("using option = ", option1, option2, option3)

This achieves my desired output (listed above), but only works for a set where i know the length. I want to expand it for a list of an arbitrary length, but am having trouble doing that. I imagine if I can get the iterative solution working, a recursive solution isn't far behind.

I don't know if BFS makes sense as a recursive function. The basic difference between DFS and BFS is that DFS uses a stack to track unvisited nodes and BFS uses a queue. Recursive DFS implementations are basically just using the call stack as that stack. Try writing a non-recursive DFS (hint: python lists can be treated like stacks), and then try replacing the stack in that implementation with a queue (You can use [`queue.Queue`](https://docs.python.org/3/library/queue.html#queue.Queue) for a FIFO queue) — Patrick Haugh, Jan 19 '18 at 04:11
@PatrickHaugh That is a good tip. wanted to flex my recursive muscles, but going to a non-recursive DFS then from there to a non-recursive BFS is a good learning process for me — The4thIceman, Jan 19 '18 at 04:16
Agree with @PatrickHaugh 100%, implementing a BFS as a recursive function would require jumping through some complicated hoops. BFS is much more naturally implemented with loops. — Turksarama, Jan 19 '18 at 04:19
That insight about DFS "using the call stack" as the data structure itself is great. — JacobIRR, Jan 19 '18 at 05:03
@Turksarama: It's not really complicated hoops; there's languages where recursion is the only available looping construct, and they obviously still can implement BFS. The problem is more that Python does not ([and never will](https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion)) support Tail Call Optimisation, so you can't do it without wasting a ton of memory. — Amadan, Jan 19 '18 at 05:31
The way to do BFS is to pass in the tail of your queue + your nodes children to your recursion function. I might actually try it and post an answer. — Turksarama, Jan 19 '18 at 05:47

Matteo T. · Accepted Answer · 2018-01-19T23:59:42.347

Edit: I did't notice from the example that all permutations was required. Follows a function that uses a list as a queue:

def bfs(options):
    queue = [([c], [*options[:i], *options[i+1:]]) for i,c in enumerate(options)]
    while len(queue) > 0:
        head, tail = queue[0]
        print(head)
        queue.extend([([*head, c], [*tail[:i], *tail[i+1:]]) for i,c in enumerate(tail)])
        del queue[0]

Which works like this (64 lines, truncated):

>>> bfs(['q','w','e','r'])
['q']
['w']
['e']
['r']
['q', 'w']
['q', 'e']
...
['r', 'w']
['r', 'e']
['q', 'w', 'e']
['q', 'w', 'r']
['q', 'e', 'w']
...
['r', 'q', 'e', 'w']
['r', 'w', 'q', 'e']
['r', 'w', 'e', 'q']
['r', 'e', 'q', 'w']
['r', 'e', 'w', 'q']

Also,

def bfs(options):
    queue = [([c], [*options[:i], *options[i+1:]]) for i,c in enumerate(options)]
    for head, tail in queue:
        queue.extend([([*head, c], [*tail[:i], *tail[i+1:]]) for i,c in enumerate(tail)])
    return [head for head, tail in queue]

this version returns a list instead of printing.

Follows the previous answer, not considering permutations:

As already said by others in the comments, it's not natural. Follows a "recursive" function:

def bfs(options, level=0):
    if level == 0:
        for c in options:
            print([c])
        for i in range(1,len(options)):
            bfs(options, i)
    else:
        for i,c in enumerate(options):
            for j,g in enumerate(options[i+1:]):
                if i+1+j+level <= len(options):
                    print([c,*options[i+1+j:i+1+j+level]])

The * in the last line requires Python3, but you can remove that.

The expected output is:

['q']
['w']
['e']
['r']
['q', 'w']
['q', 'e']
['q', 'r']
['w', 'e']
['w', 'r']
['e', 'r']
['q', 'w', 'e']
['q', 'e', 'r']
['w', 'e', 'r']
['q', 'w', 'e', 'r']

Another version:

def bfs(options, level=0):
    for i,c in enumerate(options):
        for j,g in enumerate(options[i+1:]):
            if i+1+j+level <= len(options):
                print([c,*options[i+1+j:i+1+j+level]])
            if level == 0:
                break
    if level < len(options):
        bfs(options, level + 1)

Brilliant. I had the same concept of using a level but got stuck on trying to implement a separate dict/list similar to OP's DFS. Now I can sleep... thanks. — r.ook, Jan 19 '18 at 05:46
This is a good start to the solution, but one thing: Order is relevant, so I need every possible combination. For example: [q,w] and [w,q] should appear in the list. The key i think i was missing was tracking the level. I will try to build off this today... — The4thIceman, Jan 19 '18 at 12:54
@MatteoT. Yes, that is more of less what I am looking for. It is not recursive, but after reading more about DFS and BFS i am content with using an iterative solution as a recursive BFS doesn't make a whole lot of sense. I ended up modifying your solution for more my coding style but yours works and will be marked as such. Thanks! — The4thIceman, Jan 20 '18 at 03:20

score 0 · Answer 2 · answered Jan 20 '18 at 03:42

I am posting an answer for my own question to offer some clarity regarding depth first search and breadth first search. My initial goal was a recursive breadth first version of my recursive depth first function. This came from a lack of understanding of the fundamental difference between DFS and BFS: DFS uses a stack and BFS uses a queue. (Thanks to @Patrick Haugh for the insight as well as this post: Performing Breadth First Search recursively).

The fact that DFS uses a stack lends itself well with a recursive function because you can use the call stack as your operating stack. But This doesn't work for the queue style of a BFS. Breadth First Search can be done recursively, but ends up resembling a bit of a mangled depth first search. It is much cleaner and intuitive to keep BF as an iterative function.

Never a fan of copy/pasting code without understanding why it works, @Matteo T. correct answer guided me to the iterative BFS solution without enumeration which i am currently implementing:

def bfs_iterative(options):
    queue = [[item] for item in options]
    while queue:
        using = queue.pop(0)
        print(using)
        remaining = [item for item in options if item not in using]
        extension = []
        for item in remaining:
            using.append(item)
            extension.append(using[:])
            using.pop()
        queue.extend(extension)

Python: Convert a depth first search to a breadth first search for all combinations of a list

2 Answers2

Linked