algorithm - 使用 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

您的算法似乎已经实现了回溯，这是为置换做的正确事情之一。还有基于尾部倒置的非递归算法(找不到链接，我好像记不太清名字了)或者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