使用bfs或dfs打印排列

Question

我正在尝试使用递归打印字符串的所有排列，如下所示。但是我想知道我们是否也可以使用bfs或dfs来执行此操作，我是否认为正确？

如果是，那么您能给我个主意吗？我的想法是：如果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))

队列实现在这里

Answer 1

您的算法似乎已经实现了回溯，这是对置换进行的正确操作之一。还有一种基于尾部反演的非递归算法（找不到链接，我想我不记得它的名字了）或QuickPerm算法：http ://www.quickperm.org/quickperm.html

DFS和BFS仅对每个顶点访问一次。因此，如果您真的要使用它们，则应查看排列（整个字符串，例如“ abcd”，“ abdc”等）作为顶点，而不是单独的字符（例如“ a”，“ b”等）。像“ abcd”这样的顶点，您应该尝试交换每对字符，并查看该顶点是否已被访问过。您可以将一组已访问的顶点存储在中unordered_set。因此，例如在“ abcd”中，如果交换“ b”和“ c”，则会得到“ acbd”等。此算法应产生每个排列，因为对于Heap的算法，在每个步骤中只需交换一对顶点即可：https：// zh.wikipedia.org/wiki/Heap%27s_algorithm