permutations.cpp

Find all permutations! The code is actually C, but written in C++. The explanation of the code lies in the link I provide below.

per.cpp

void swap(char *fir, char *sec)
{
    char temp = *fir;
    *fir = *sec;
    *sec = temp;
}

/* arr is the string, curr is the current index to start permutation from and size is sizeof the arr */
void permutation(char * arr, int curr, int size)
{
    if(curr == size-1)
    {
        for(int a=0; a<size; a++)
            cout << arr[a] << "\t";
        cout << endl;
    }

    else
    {
        for(int i=curr; i<size; i++)
        {
            swap(&arr[curr], &arr[i]);
            permutation(arr, curr+1, size);
            swap(&arr[curr], &arr[i]);
        }
    }
}

int main()
{

    char str[] = "abcd";

    permutation(str, 0, sizeof(str)-1);
    return 0;
}

This code was copied by this link. The code is not mine and I have it here for quick reference.

Once I needed to store the results in an std::vector, without the duplicates. Here is the (dirty) code.

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

void swap(char *fir, char *sec)
{
    char temp = *fir;
    *fir = *sec;
    *sec = temp;
}

/* arr is the string, curr is the current index to start permutation from and size is sizeof the arr,
  v the std::vector and d the option to allow duplicates or not */
void permutation(char * arr, int curr, int size, vector<string>& v, bool d)
{
    if(curr == size-1)
    {
	bool duplicate = false;
	string temp = "";
        for(int a=0; a<size; a++)
            temp += arr[a];
        for(size_t i = 0 ; d && i < v.size() ; ++i)
	    if(v[i] == temp)
		duplicate = true;
        if(!duplicate)
	    v.push_back(temp);
    }
    else
    {
        for(int i=curr; i<size; i++)
        {
            swap(&arr[curr], &arr[i]);
            permutation(arr, curr+1, size, v, d);
            swap(&arr[curr], &arr[i]);
        }
    }
}

int main()
{
    char str[] = "bababa";
    vector<string> v;	//holds the permutations
    v.reserve( 1 << (sizeof(str)-1) );
    bool d = true; // allow duplicates

    permutation(str, 0, sizeof(str)-1, v, d);
//    for(size_t i = 0 ; i < v.size() ; ++i)
//	cout << v[i] << endl;
    cout << "Number of permutations: " << v.size() << endl;

    return 0;
}

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s