Thread: k-permutations

Hey,

I'm having some trouble in finding a solution for this problem. Which is:

I need a function that given an array with a number of elements n, and a positive integer k <= n, returns the next k-permutation of the array.

For example if k=2, the array (1,2,3) would have the following permutations:

1 2
1 3
2 1
2 3
3 1
3 2

I am not sure if they would be generated in this order, but that's not relevant as long as there are no repetitions.

Thankyou

Regards,

miguel.pinr

Permutation - Wikipedia, the free encyclopedia

search google for 'generate permutations lexicographic order'
note that the data has to be sorted first

Found a C++ (bad code) in my example but it gets the job done.
I transformed it in C.

Code:

#include <stdio.h>

int array[10] = {0,1,2,3,4,5,6,7,8,9};


void swap(int x, int y){
    int temp = array[x];
    array[x]=array[y];
    array[y]=temp;

    return;
}

void printArray(int size){
    int i;

    for (i=0;i<size;i++)
        printf("%d ",array[i]);

    printf("\n");

    return;
}

void permute(int k,int size){
    int i;

    if (k==0)
        printArray(size);
    else{
        /* We do it recursively */
        for (i=k-1;i>=0;i--){
            swap(i,k-1);
            permute(k-1,size);
            swap(i,k-1);
        }
    }

    return;
}

int main(void){

    permute(3,3);

    return 0;
}

If you understand what permutations are , then this code is pretty clear

Also welcome to the forum.

PS - i just googled how to generate k-permuatations in c ... Try it yourself next time

I have seen that code before, and it's not what i need, the problem with it is that you generate all nPk permutations with n=k, and then you only print the first k numbers of the array, and so you are computing a lot more swap operations wich are not necessary, what i really need is to only generate the permutations of k size, from a set o n elements the ones which total number is given by the formula: n!/(n-k)!

Thanks anyaway ;-)