Full Permutation

Several permutation functions:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void printa(int a[], int n)
{
    for(int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void p1(int a[], int m, int n)
{
    if(m == n)
    {
        printa(a, n);
    }
    else
    {
        for(int i = 0; i < n; ++i)
        {
            a[m] = i;
            p1(a, m + 1, n);
        }
    }
}

void p2(int a[], int m, int n)
{
    if(m == n)
    {
        printa(a, n);
    }
    else
    {
        for(int i = m; i < n; ++i)
        {
            swap(a[i], a[m]);
            p2(a, m + 1, n);
            swap(a[i], a[m]);
        }
    }
}

bool p3_p(int a[], int n)
{
    int i = 0;
    for(i = n - 2; i >= 0; --i)
    {
        if(a[i + 1] > a[i])
            break;
    }
    if(i < 0)
        return false;
    int m = i;
    ++i;
    for(; i < n; ++i)
    {
        if(a[i] <= a[m])
        {
            --i;
            break;
        }
    }

    if(i == n)
        --i;

    swap(a[i], a[m]);
    sort(a + m + 1, a + n);
    printa(a, n);
    return true;
}

void p3(int a[], int n)
{
    sort(a, a + n);
    printa(a, n);
    while(p3_p(a, n));
}

void p3_stl(int a[], int n)
{
    sort(a, a + n);
    do
    {
        printa(a, n);
    }while(next_permutation(a, a+ n));
}

int wmain(int argc, wchar_t* argv[])
{
    printf("p1:\n");
    int a[] = {0, 0, 0};
    p1(a, 0, _countof(a));
    printf("\n");

    printf("p2:\n");
    int b[] = {0, 1, 2};
    p2(b, 0, _countof(b));
    printf("\n");

    printf("p3:\n");
    int c[] = {0, 1, 2};
    p3(c, _countof(c));
    printf("\n");

    printf("p3_stl:\n");
    int d[] = {0, 1, 2};
    p3_stl(d, _countof(d));
    printf("\n");

    return 0;
}

The output:

p1:
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

p2:
0 1 2
0 2 1
1 0 2
1 2 0
2 1 0
2 0 1

p3:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

p3_stl:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Function p1 answers following question: there are n buckets, each bucket has n balls each labeled 0 to n-1. How many possible combinations would you get if one ball was picked from each bucket randomly?

Function p2 is a full permutation algorithm using recursion; p3 is also a full permutation algorithm without recursion, and p4 shows how to use the function provided by STL.


Advertisements

Posted on June 12, 2012, in Uncategorized. Bookmark the permalink. Leave a comment.

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

%d bloggers like this: