使用 bfs 或 dfs 打印排列

Question

我正在尝试使用递归打印字符串的所有排列，如下所示。但我想知道我们是否也可以使用 bfs 或 dfs 来做到这一点，我的想法对吗？

如果是，那么你能给我一个想法吗？我的想法是：if string = "abcd" 起始节点：'a' 结束节点：'d' 中间节点：'b' 和 'c'

然后我们可以将起始节点更改为 'b'、'c' 和 'd'。

我很难将其可视化并放入算法中。

#include <stdio.h>

void swap(char *s, int i, int j)
{
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

void foo(char *s, int j, int len)
{
    int i;
    if (j == len-1) {
        printf("%s\n", s);
        return;
    }
    for (i=j;i<len;i++) {
        swap(s, i, j);
        foo(s, j+1, len);
        swap(s, i, j);
    }
}

int main()
{
    char s[] = "abc";
    foo(s, 0, strlen(s));
}

根据Serge Rogatch给出的逻辑，可以解决以下问题：

def swap_two(s, i, j):
    return s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]

def swaps(s):
    for i in range(1, len(s)):
        yield swap_two(s, 0, i)

def print_permutations(input, q):
    seen_list = []
    q.enqueue(input)
    while not q.isempty():
        data = q.dequeue()
        for i in swaps(data):
            if i not in seen_list:
                q.enqueue(i)
                seen_list.append(i)
    return seen_list
q = queue(512)
seen_list = print_permutations("abcd", q)
print(sorted(seen_list), len(seen_list))

队列实现是here

Answer 1

您的算法似乎已经实现了回溯，这是为置换做的正确事情之一。还有基于尾部倒置的non-recursive算法（没找到link，我好像记不太清名字了）或者QuickPerm算法：http://www.quickperm.org/quickperm.html

DFS 和 BFS 只访问每个顶点一次。因此，如果您真的想使用它们，那么您应该将排列视为顶点（整个字符串，如 "abcd"、"abdc" 等），而不是单独的字符，如 'a'、'b', 等等。从一些像 "abcd" 这样的初始顶点开始，你应该尝试交换每对字符，看看那个顶点是否已经被访问过。您可以将访问过的顶点集存储在 unordered_set 中。所以例如在 "abcd" 中，如果你交换 'b' 和 'c' 你会得到 "acbd" 等。这个算法应该产生每个排列，因为对于 Heap 的算法，它足以交换每个中的一对顶点步骤：https://en.wikipedia.org/wiki/Heap%27s_algorithm

Answer 2

您可以阅读这篇文章：

http://en.cppreference.com/w/cpp/algorithm/next_permutation

尽管这是 C++ 实现，但您可以轻松地将其转换为 C 版本

顺便说一句，你的方法可以称为dfs！

Answer 3

如果你真的想模拟图遍历算法...这里有一个直观的（可能不是最优雅的）方法：

将字符串想象成一个图形，其中每个字符都与其他每个字符相连
与其尝试从源到目的地寻找 "path"，不如将问题框定如下："find all paths of a specific length - from every source"

所以从第一个字符开始，把它当作"source"；然后找到所有长度为整个字符串长度的路径...然后使用下一个字符作为源...

这是 python 中的一个实现：

def permutations(s):
    g = _str_to_graph(s) # {'a': ['b', 'c'], 'b': ['c', 'a'], 'c': ['a', 'b'] }
    branch = []
    visited = set()
    for i in s: # use every character as a source
        dfs_all_paths_of_certain_length(i, len(s), branch, visited, g)

def _str_to_graph(s):
    from collections import defaultdict
    g = defaultdict(list)
    for i in range(len(s)):
        for j in range(len(s)):
            if i != j:
                g[s[i]].append(s[j])
    return g

def dfs_all_paths_of_certain_length(u, ll, branch, visited, g):
    visited.add(u)
    branch.append(u)
    if len(branch) == ll: # if length of branch equals length of string, print the branch
        print("".join(branch))
    else:
        for n in g[u]:
            if n not in visited:
                dfs_all_paths_of_certain_length(n, ll, branch, visited, g)
    # backtrack
    visited.remove(u)
    branch.remove(u)

使用 bfs 或 dfs 打印排列

printing the permutation using bfs or dfs

algorithm

permutation

breadth-first-search

depth-first-search