Permutation - Page 3

[hinduengg]

Dump the loops, what you need is a recursive algorithm which would work for arbitrary lengths of arrays. One of the way is using 'Heap Permute'. Here is a sample program which you can easily adapt to use with C style strings:

// Untested

const int SIZE = 4;
static int counter = 1;

void swap(int arr[], int one, int two)
{
    int tmp = arr[one];
    arr[one] = arr[two];
    arr[two] = tmp;
}

void print(int arr[])
{
    for(int i = 0; i < SIZE; ++i)
    {
        cout << arr[i] << "  ";
    }
    cout << " ------->  " << counter++;
    putchar('\n');
}

void permute(int arr[], int size)
{
    if(size == 1)
    {
        print(arr);
    }
    else
    {
        for(int i = 0; i < size; ++i)
        {
            permute(arr, size - 1);
            if(size % 2 == 1)
                swap(arr, 0, size - 1);
            else
                swap(arr, i, size - 1);
        }
    }
}

int main()
{
    int myArr[SIZE] = {1, 2, 3, 4};
    permute(myArr, SIZE);
    cin.get();
}

I am wondering whether I am right or not, is it that one can call the function from its own code block , because I have been taught that one can call a function from any other function or from main().

I did not understand

void permute(int arr[], int size)
{
    if(size == 1)
    {
        print(arr);
    }
    else
    {
        for(int i = 0; i < size; ++i)
        {
            permute(arr, size - 1);// function call from within the same function:(
            if(size % 2 == 1)
                swap(arr, 0, size - 1);
            else
                swap(arr, i, size - 1);
        }
    }
}

[~s.o.s~]

A function with a base case(the terminating condition) and a recursive case, calling itself is known as Recursion. So whats basically happening in the above case is that to tackle the problem of the generation of result set which grow exponentially, and to simplify the solution, I decided to call the same function within itself seeing that each run of the function would generate a permutation for me.

Maybe you should wait a bit longer before submitting this solution or start reading your text book or the ample resources on the internet. :-)

[hinduengg]

To Lerner ,

The code posted by you is not giving the output that I long for now.

Perhaps now I should end this discussion for no concrete thing has been achieved I will show my professor what I have done . See you all in my next new topic This thread is perhaps too long. My original code could not be made but I tried my best.

Thanks to each one of you,
hinduengg