печать перестановки с использованием bfs или dfs

Question

Я пытаюсь напечатать все перестановки строки, используя рекурсию, как показано ниже. Но мне было интересно, можем ли мы использовать bfs или dfs для этого, думаю, правильно?

Если да, то можете ли вы, пожалуйста, дать мне представление? Моя идея: если строка = «ABCD» начального узла: «а» конечный узел: «d» промежуточные узлы: «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)); 
} 

Исходя из логики данного Сержем 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» и т. д. Этот алгоритм должен вызывать каждую перестановку, потому что для алгоритма Кучи достаточно менять только одну пару вершин на каждом шаге: https://en.wikipedia.org/wiki/Heap%27s_algorithm

Answer 2

0 может прочитать эту статью:

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

Хотя это реализация C++, но вы можете легко превратить его в C версии

Кстати, ваш метод можно назвать ДФС!