k-permutations

This is a discussion on k-permutations within the C Programming forums, part of the General Programming Boards category; Hey, I'm having some trouble in finding a solution for this problem. Which is: I need a function that given ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    2

    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

  2. #2
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    Permutation - Wikipedia, the free encyclopedia

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

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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

  4. #4
    Registered User
    Join Date
    Nov 2012
    Posts
    2
    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 ;-)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By HotBowlofSoup in forum C++ Programming
    Replies: 3
    Last Post: 03-20-2010, 08:29 PM
  2. Permutations
    By rocketman03 in forum C++ Programming
    Replies: 1
    Last Post: 11-02-2009, 05:21 AM
  3. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  4. permutations
    By computation in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 02:46 PM
  5. Permutations
    By mekaj in forum C++ Programming
    Replies: 5
    Last Post: 01-23-2006, 08:10 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21