CODEWITHSUNDEEP
algorithmpermutationbreadth-first-searchdepth-first-search
noman pouigt
noman pouigt

Reputation: 976

printing the permutation using bfs or dfs

I am trying to print all the permutations of a string using recursion as below. But I was wondering if we can use bfs or dfs also to do this, am I thinking right?

If yes, then can you please give me an idea? My idea is: if string = "abcd" start node: 'a' end node: 'd' intermediate nodes: 'b' and 'c'

We can then change the start nodes to 'b','c' and 'd'.

I am having difficulty in visualizing it to put it in a algorithm.

#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));
}

Based on the logic given by Serge Rogatch, below problem can be solved:

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

queue implementation is here

Upvotes: 1

Views: 8463

Answers (3)

labheshr
labheshr

Reputation: 3056

If you strictly want to emulate a graph traversal algorithm...Here's an intuitive(probably not the most graceful) approach:

  1. Think of string as a graph, where each character is connected to every other character

  2. Instead of trying to find a "path" from source to destination, frame the problem as follows: "find all paths of a specific length - from every source"

So start from the first character, use it as the "source"; then find all paths with length = length of the entire String... Then use the next character as the source...

Here's an implementation in 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)

Upvotes: 1

Serge Rogatch
Serge Rogatch

Reputation: 15070

Your algorithm seems to already implement backtracking, which is one of the correct things to do for permuting. There is also non-recursive algorithm based on tail inversion (can't find the link, I think I don't remember its name precisely) or QuickPerm algorithm: http://www.quickperm.org/quickperm.html

DFS and BFS visit every vertex exactly once. So if you really want to use them, then as vertices you should view permutations (whole strings like "abcd", "abdc", etc.) rather than separate characters like 'a', 'b', etc. Starting with some initial vertex like "abcd" you should try to swap each pair of characters and see if that vertex has been already visited. You can store the set of visited vertices in an unordered_set. So e.g. in "abcd" if you swap 'b' and 'c' you get "acbd" etc. This algorithm should produce each permutation because for Heap's algorithm it suffices to swap just one pair of vertices in each step: https://en.wikipedia.org/wiki/Heap%27s_algorithm

Upvotes: 5

kaitian521
kaitian521

Reputation: 578

You can read this article:

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

AlTHOUGH this is C++ implementation, but you can easily transform it to a C version

By the way, your method can be called a dfs!

Upvotes: -1

Related Questions