C Codes

Generate Permutations – Decrease and Conquer

Uses the definition of n! to generate the permutations.

Idea: Remove each item from the given n items one at a time and append it to remaining (n-1)! permutations.

Efficiency: O(n!) and as well we have expensive swaps

Strategy used: Decrease and Conquer(decrease by 1)


#include 
#include 

// Global n
int gn;

void permute(int a[], int n)
{
    if (n == 1)
    {
        int i;
        for(i = 0; i < gn; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }

    int i;
    int temp;
    for(i = 0; i < n; i++)
    {
        // Remove the ith item
        temp = a[i];
        a[i] = a[n-1];
        a[n-1] = temp;

        permute(a, n-1);

        // Restore it for the next round
        temp = a[i];
        a[i] = a[n-1];
        a[n-1] = temp;

    }
}

int main()
{
    int a[5] = {1, 2, 3};
    int n = 3;
    gn = n;

    permute(a, n);

    return 0;
}
Advertisements

One thought on “Generate Permutations – Decrease and Conquer

Let me Know What you Think!

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s