使用bfs或dfs打印排列

Question

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

如果是的话，那么请你给我一个想法吗？我的想法是：if string =“abcd”start node：'a'end node：'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

您的算法似乎已经实现了回溯，这是进行置换的正确方法之一。还有基于尾部反转的非递归算法（找不到链接，我想我不记得它的名字正确）或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

如果您严格要模拟图遍历算法......这是一种直观的（可能不是最优雅的）方法：

1. 将字符串视为图形，其中每个字符都连接到其他每个字符
2. 不是试图从源到目的地找到“路径”，而是按如下方式构建问题：“从每个来源找到特定长度的所有路径”

所以从第一个角色开始，用它作为“源”;然后找到所有路径长度=整个字符串的长度...然后使用下一个字符作为源...

这是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)

Answer 3

你可以阅读这篇文章：

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

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

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