CareerCup

void print_all_combination(string str, string comb)
{
if (str.size() == 0) cout << comb << endl;
else {
for (int i = 0; i < str.size(); i++) {
string newcomb = comb + str[0];
string newstr = str.substr(1);
print_all_combination(newstr, newcomb);
rotate(str.begin(), str.begin()+1, str.end());
}
}
}


print_all_combination("amazon", "");

This can further be optimized. For eg: i am creating a local var everytime. you can play with references to be more space efficient. The logic behind permutation is like the one above.

Comments/criticisms welcome.

Thanks,
Rohith Menon.

#include <iostream>
#include <string>

//the end of permutation is when the array is in reverse order
template<class RandomAccessIterator>
bool next_permutation(RandomAccessIterator begin, RandomAccessIterator end)
{

    RandomAccessIterator it = end-1;

    // find the position where [it, end) is in reverse order
    while((--it)!= begin && !(*it < *(it+1))  );


    bool end_of_permutation = (it == begin);

    if(end_of_permutation) // restart the permutation
        std::reverse(begin, end);
    else{
        // find the smallest one that is larger than *it
        RandomAccessIterator it2 = it;
        while((++it2 != end) && *it < *it2);
        --it2;

        std::swap(*it, *it2);
        std::reverse(it+1, end); // make [it+1, end) to the ascending order
    }

    return end_of_permutation;
}

int main()
{
std::string s("amazon");

do
{
    next_permutation(s.begin(), s.end());
    std::cout << s << std::endl;

}while(s!="amazon");
}

Looks like you're printing out permutations aren't you?

I think this code doesnt take care of permutation with repetition...
amazon has 2 a's in it and each string will be printed twice.....

comb(amazon)=comb(amzon)+{aa} U comb(mzon).
only for this problem.

<pre>&nbsp;</pre><pre>&nbsp;</pre><pre><span style="color: #008000">//string combinations</span>

#include &lt;iostream&gt;
#include &lt;<span style="color: #0000ff">string</span>&gt;
<span style="color: #0000ff">using</span> std::<span style="color: #0000ff">string</span>;


<span style="color: #0000ff">int</span> freq[256] ; <span style="color: #008000">// frequency table</span>
<span style="color: #0000ff">int</span> total;
<span style="color: #0000ff">void</span> comb(<span style="color: #0000ff">int</span> step, <span style="color: #0000ff">string</span> &amp;z) {
<span style="color: #0000ff">if</span> (step == 0) {
std::cout &lt;&lt; total++ &lt;&lt; "<span style="color: #8b0000">:</span>"&lt;&lt;z &lt;&lt; std::endl;
<span style="color: #0000ff">return</span>;
}

<span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i = 0; i &lt; 256; ++i) {
<span style="color: #0000ff">if</span>(freq[i]) {
-- freq[i];
comb(step - 1, z + <span style="color: #0000ff">char</span>(i));
++ freq[i];
}
}
}

<span style="color: #0000ff">int</span> main() {
<span style="color: #0000ff">string</span> s;
<span style="color: #0000ff">while</span>(std::cin &gt;&gt; s) {

memset(freq, 0, <span style="color: #0000ff">sizeof</span>(freq));
total = 1;
<span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i = 0; i &lt; s.length(); ++i)
++ freq[s[i]];

<span style="color: #0000ff">string</span> z;
comb(s.length(), z);

}

}</pre>

What should I do of all the codes debug it ... ???
Please this is the humble request for all you geniuses around -- give logic to 1 line wont do any harm will it

@redroof on November 16
WTF are you trying to print? Is it asked to print html/js stuffs? Oh Jesus!
Please read the question properly before posting anything. If you don't know the answer avoid putting junk codes. That's a bullsh** man! You suck.

I completely agree with your opinion @ Anonymous.
Anyone writing big chunk of codes should put a couple of lines as explanation else there's no point putting such craps as no one is going to read and make any sense out of it.

/*

This program gives the permutation of any given string, and avoids repeated permutations because of duplicate characters

*/

#include<iostream>
using namespace std;
string insert( char c, int n, string s ){
string temp = "";
for( int i = 0; i < n; i++ ) temp += s[i];
temp += c;
for( int i = n; i < s.length(); i++ ) temp += s[i];
return temp;
}
void perm( string s1, string s2 ){
int l1 = s1.length();
int l2 = s2.length();
if( l1 == 0 ) { cout << s2 << endl; return; }
for( int i = 0; i <= l2; i++ ){
if( s1[ l1 - 1 ] == s2[ i - 1 ] ) continue; // This check avoids all the repetitions :)
perm( s1.substr( 0, l1 - 1 ), insert( s1[ l1 - 1 ], i, s2 ) );
}
}
int main(){
string s = "aaaaa";
string ans = "";
perm( s, ans );
}

//string combinations

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


int freq[256] ; // frequency table
int total;
void comb(int step, string &z) {
if (step == 0) {
std::cout << total++ << ":"<<z << std::endl;
return;
}

for(int i = 0; i < 256; ++i) {
if(freq[i]) {
-- freq[i];
comb(step - 1, z + char(i));
++ freq[i];
}
}
}

int main() {
string s;
while(std::cin >> s) {

memset(freq, 0, sizeof(freq));
total = 1;
for(int i = 0; i < s.length(); ++i)
++ freq[s[i]];

string z;
comb(s.length(), z);

}

}