permutations without recursion????

[ashworcp]

Hi, I wrote a program that created all the permutations of a given string. I'm trying to modify it to not use recursion while using a queue. I am not sure how to do this... any help will be appreciated! Here is my code:

vector<string> generate_substrings(string s)
{
    vector<string> result;
    if(s.length()==0) result.push_back(s);
    else 
    {
        for(int j = 0; j <= s.length(); j++)
        {
            cout << s.substr(0,j) << " ";
        }
        generate_substrings(s.substr(1,s.length()-1));
    }
    system("Pause");
    return result;
}

int main()
{
    vector<string> result;
    cout << "Please enter a word: ";
    string word;
    cin >> word;
    generate_substrings(word);
    cout << endl;
    return 0;
}

[shacktar]

You can solve the problem as follows.

Given the string, W, and the length, L, find all permutations of the set I = {0, 1, 2, ... , L - 1}

And

Given a permutation P = {i(1), i(2), ..., i(L-1)}, of I, then a permutation of W is given by the concatenation of W.at(i(1)), W.at(i(2)), ... , W.at(i(L-1))

Example:

W = Dog
L = 3

'D' -> 0, 'o' -> 1, 'g' -> 2

All possible permutations of {0, 1, 2}:
012
021
120
102
201
210

(which represent the following strings):
Dog
Dgo
ogD
oDg
gDo
goD

Thus, the problem becomes simply, how to find all possible permutations of this set {0,1,2,...,N} (non-recursively)?

This problem has been extensively studied and there is a plethora of information online.

[ultifinitus]

You can use my solution with a for loop.

[ashworcp]

@ultifinitus what is your solution??

[ashworcp]

If your talking about your blog, you are using recursion and I am trying to make it non recursive.

[kev82]

std::next_permutation

[ashworcp]

@ kev82 I can't use that

[kev82]

Why not? Unless of course this is homework, in which case someone posting the code to an algorithm you don't fully understand won't really help you learn.

That aside, I'm haven't got the faintest idea how you would do it without recursion and with only a queue.

[ashworcp]

I think it should be done like this:

//read in lines
//step 1. set copy equal to temp
//step 2. find the char in copy that you want to work with
//step 3. erase that char from the string
//step 4. insert that char before the plus sign
//step 5. push to the queue

[morus]

I'm a bit confused. Your code does not compute a permutation but only all subsets of a string, right?

[h9uest]

This is a typical problem in a data structure and algorithm course, and fortunately (of course, otherwise we wouldn't call it typical), there is a breadth-first search approach, which can be in turn implemented with the "queue" data structure.

Part 1: What's the idea?
The idea is: if you treat every character as a node of a complete graph, then the permutation problem becomes the problem of graph traversal. You need to find all routes that can traverse the graph. This is a very typical problem that has been studied.

Part 2: How do we represent the graph?
You could use adjacent matrix, for example, to represent the graph. Other options, such as adjacent list, might not be the best idea in terms of time complexity. But I believe you could still do it, if you insist.

Part 3: How do we implement breadth first search with queue?
I guess this is what you're learning at the moment, isn't it? Otherwise you professor/tutor might not want you modify the recursive solution into a queue based one. When you are at a node, you add nodes around it into the queue, then pop one out; repeat this until finished. Pay attention to nasty details in implementation.



Personally, I think it would be a good exercise to implement the graph traversal with depth first search as well, because it will serve as a contrast/comparison with breadth first search. How do we do that? You might want to use stack, for example.


Good luck.