-
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 ;-)