This article uses wide search to solve the full permutation problem. My last article introduced the method of using deep search to solve the full permutation problem in detail.

Total permutation problem

Given a sequence without repeating digits, return all possible permutations. For example, the sequence [1, 2, 3] its permutations for [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

In fact, when searching for solutions to the full array problem on the Web, most of the answers are solved using depth-first search, because depth-first search is easier to understand than breadth-first search, as shown below.

To explore breadth-first search, we need to turn to another image and ask, how can we achieve the layer-by-layer traversal shown in the figure?

We use a queue data structure to implement breadth-first search, initially enqueuing [1], [2], [3].

Consider the case where the current node is [1] : Pop [1] from the head of the queue and traverse the NUMS array looking for the second digit in the permutation. Easy to get in nums = [1,2,3],2 and 3 can be used as the second digit in the permutation. So [1,2], [1,3] join the team.

Continue to consider the current node for [2], [3], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2] all the team.

It then pops the queue header [1,2] and iterates through the nums array looking for the third digit in the array, so [1,2,3], [1,3,2] join the queue… All permutations are searched until the last three permutations [3,2,1] enter the team.

The code implementation is as follows.

def solution(nums) :
    queue = [[i] for i in nums]
    ans = [nums]	# avoid nums with only one element. TMP not in ans
    while queue:
        status = queue.pop(0)
        for i in nums:
            if i in status:
                continue
            tmp = status + [i]
            if len(tmp) == len(nums) and tmp not in ans:
                ans.append(tmp)
            else: queue.append(tmp)
    return ans

print solution([1.2.3])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Copy the code

Try printing the intermediate state of the solution function to see why this iterative approach is called breadth-first search.

This article sample title and Leecode 46. All arranged in the same, readers can try to submit, verify the correctness of their own code.