string permutation lexicographic order problem

[globaltourist]

I am pretty much a beginner in c++ and wanted a little challenge so i decided to make a program to print out all permutations of a string in a lexicographic order even if the input
isn't in a lexicographic order and cant think of a solution to a problem i encountered.

the code:

#include<iostream>
#include<string>
using namespace std;

void swap(char *a, char *b)
{
*a = *a - *b;
*b = *b + *a;
*a = *b - *a;
}

string sort(string str)
{
for (int i = 0, n = 0; n < str.length();)
{
if (str[i] > str[i + 1])
{
swap(str[i], str[i + 1]);
n = 0;
}
else
++n;
(i < (str.length() - 2)) ? ++i : i = 0;
}
return(str);
}

void premute(string str, int a)
{
int i;
if (a == (str.length()-1))
cout << str << "\n";
else
{
for (i = a; i < str.length(); ++i)
{
swap(str[a], str[i]);
premute(str, a + 1);
swap(str[a], str[i]);
}
}
}

int main()
{
string sequence;
cout << "enter a sequence of charecters\n";
cin >> sequence;
sequence = sort(sequence);
premute(sequence, 0);
cin >> sequence;
}

the problem is if i input "abc"

i get:
abc
acb
bac
bca
cba <-- out of order here
bac

and with "abcd" it is even worse.

i know that the recursion tree should print it out that way but is it possible to fix it without fancy libraries in my current code?

[48bpfSEw]

I run your code in http://cpp.sh/
and it works very well!

enter a sequence of charecters
abc

result:

abc
acb
bac
bca
cba
cab

[globaltourist]

yes but the problem is that:

cba
cab

isn't in a lexicographic order as it should be the opposite:

cab
cba

and i have no idea how to fix it :(
+ i'm sure my string sort function isn't efficient at all and need help on simplifying it and i
don't want to use a made c/c++ library but rather create my own function to learn better and it is the challenge requirements aswell.

[48bpfSEw]

A good programming technique is to throw away the current solution and start again to solve the problem.



Here is an working permutation code:

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void permute(string select, string remain){
    if(remain == ""){
        cout << select << endl;
        return;
    }
    for(int i=0;remain[i];++i){
        string wk(remain);
        permute(select + remain[i], wk.erase(i, 1));
    }
}

int main(){
    string anagrama;
    cout << "input character set >";
    cin >> anagrama;
    sort(anagrama.begin(), anagrama.end());
    permute("", anagrama);
}

input character set >abc
abc
acb
bac
bca
cab
cba


found on : http://stackoverflow.com/questions/17396222/how-to-generate-all-permutations-of-an-array-in-sorted-order

[globaltourist]

thanks man but i didn't want to use any fancy libraries but make the functions my self :(

[48bpfSEw]

https://www.youtube.com/watch?v=swIQZZCZ7rw

[globaltourist]

how did you know i like that song 0_0

[48bpfSEw]

because I like it too! ^^

Here is the solution of your problem:

http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

You have now to look for an algorithm to sort the result.

http://www.cplusplus.com/articles/NhA0RXSz/

Store your strings in a vector and call sort()

[globaltourist]

thanks for trying to help but it doesn't help me improve my code it replaces it instead :(