Permutation program

This is a discussion on Permutation program within the C Programming forums, part of the General Programming Boards category; I'm writing a program to print out all permutations of a given set of numbers in a random order i.e. ...

  1. #1
    Registered User C_Nik's Avatar
    Join Date
    Dec 2011
    Location
    Planet Earth
    Posts
    18

    Question Permutation program

    I'm writing a program to print out all permutations of a given set of numbers in a random order i.e. if the user selects 3 then it should print: (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1) and (2,1,0)
    In my code I'm not getting all of the numbers that it's supposed to print. If I enter 3 I get: (2,1,2), (1,0,1),(0,1,0),(1,2,1),(2,1,2),(1,0,1)
    Can anyone give me guidance on this algorithm? Thanks in advance...
    Code:
    #include <stdio.h>
    
    int main()
    {
        // initialization of variables
        int Choice, Number, Temp;
        
        // counters
        int index, j, k;
        int Sets = 1;
        
        printf("What number would you like to go to?\n");
        scanf("%d", &Choice);
        
        
        // initialize array after choice is made
        int NumArray[Choice];
        
        // zero out array
        for(index=0; index<Choice; index++)
        {
            
            NumArray[index]=0;
        }
        
        // fill up array with numbers
        for(index=0; index<Choice; index++)
        {
            Number = index;
            NumArray[index] = Number;
        }
        
        // get number of sets
        for(index=Choice; index>0; index--)
        {
            Sets = Sets * index;
        }
        
        // permutation algorithm
        for(index=0; index<Sets; index++)
        {
            for(j=0; j<Choice; j++)
            {
                
                for(k=Choice; k>0; --k)
                {
                    
                    Temp = NumArray[j];
                    NumArray[j] = NumArray[k];
                    NumArray[k] = Temp;
                    
                }
                
                printf("%d",Temp);
                
            }
            
            printf("\n");
            
        }
        
        printf("There are %d possible sets!\n", Sets);
        return 0;
    }
    Last edited by C_Nik; 12-17-2012 at 01:04 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I haven't seen that algorithm before. I have a sorting algorithm that is VERY close to that (minus the outermost for loop). Interesting.

    *Where did you get this algorithm? They might have named it?

    *Why would you want the output in "random" order? Most would want it in sorted order, or as fast as possible, in any order, but I've never seen a request for permutations in random order.

    You continue to surprise me. LOL

  3. #3
    Registered User C_Nik's Avatar
    Join Date
    Dec 2011
    Location
    Planet Earth
    Posts
    18
    LoL I'm thinking it is a sorting algorithm. It doesn't have to be in random order, if there is a similar sorting algorithm that probably what I need to use. Decrementing the outermost loop is what I'm looking for?

  4. #4
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,384
    Quote Originally Posted by C_Nik View Post
    LoL I'm thinking it is a sorting algorithm. It doesn't have to be in random order, if there is a similar sorting algorithm that probably what I need to use. Decrementing the outermost loop is what I'm looking for?
    What research have you done so far?

    When creating a new program, it is very important you look at pages like Permutation - Wikipedia, the free encyclopedia to make sure you are not missing anything
    Fact - Beethoven wrote his first symphony in C

  5. #5
    Registered User C_Nik's Avatar
    Join Date
    Dec 2011
    Location
    Planet Earth
    Posts
    18
    Thats the page I used to get the formula for finding the number of sets. But I'll read it again to see if I missed another statement.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by C_Nik View Post
    Thats the page I used to get the formula for finding the number of sets. But I'll read it again to see if I missed another statement.
    So from that Wiki page, you are looking for a Fisher-Yates shuffle, for random permutations, right? Have you seen this page?
    Fisher

    I don't have that one, oddly. I have the "SJT" (aka "Bell Ringers") generator, which uses simple swaps - but they're NOT anything like random permutations.

  7. #7
    Registered User C_Nik's Avatar
    Join Date
    Dec 2011
    Location
    Planet Earth
    Posts
    18
    Ok Thanks Adak! I'm going to check this out. Learning something new everyday! I appreciate this!

  8. #8
    Registered User C_Nik's Avatar
    Join Date
    Dec 2011
    Location
    Planet Earth
    Posts
    18
    I'm getting different permutations but I get repeats... Anybody have any suggestions on how I can stop the repeats? I was thinking sending to another array and comparing...

    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    
    
    int main()
    {
        // initialization of variables
        int Choice, Number, temp;
        
        // counters
        int index, j, k;
        int Sets = 1;
        
        //sets up randomized counter
        srand(time(NULL));
        
        printf("What number would you like to go to?\n");
        scanf("%d", &Choice);
        
        
        // initialize array after choice is made
        int NumArray[Choice];
        
        // zero out array
        for(index=0; index<Choice; index++)
        {
            
            NumArray[index]=0;
        }
        
        // fill up array with numbers
        for(index=0; index<Choice; index++)
        {
            Number = index;
            NumArray[index] = Number;
        }
        
        // get number of sets
        for(index=Choice; index>0; index--)
        {
            Sets = Sets * index;
        }
        
        // permutation algorithm
        for(index=Sets; index>0; index--)
        {
            
            for(j=Choice-1; j>=0; j--)
            {
                
                k = rand() % (j+1);
                temp = NumArray[k];
                NumArray[k] = NumArray[j];
                NumArray[j] = temp;
                
                printf("%d", temp);
                
            }
            
            printf("\n");
            
        }
        
        printf("There are %d possible sets!\n", Sets);
        return 0;
    }

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Can you print out a very simple table like the Wiki page I linked to above has, (along with a getchar() perhaps), and see where the error is?

    I'm not able to spot an obvious error, but this algorithm is a fragile one.

    You are doing the in-place (Durstenfeld) version, right?

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by C_Nik View Post
    I'm getting different permutations but I get repeats... Anybody have any suggestions on how I can stop the repeats? I was thinking sending to another array and comparing...
    If you want to get all permutations as you stated in post #1, generating the permutations randomly isn't a good idea IMHO.

    Code:
    // zero out array
    for(index=0; index<Choice; index++)
    {
        NumArray[index]=0;
    }
        
    // fill up array with numbers
    for(index=0; index<Choice; index++)
    {
        Number = index;
        NumArray[index] = Number;
    }
    Setting all elements to zero is useless if you immediately afterward assign other values to them.

    Bye, Andreas

  11. #11
    Registered User C_Nik's Avatar
    Join Date
    Dec 2011
    Location
    Planet Earth
    Posts
    18
    @AndiPersti: Thanks I deleted that from my code since it was superfluous..
    @Adak: Yea i was using the Durstenfeld version. It prints a simple table no problems

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Can you post up a simple example of it with the table, that shows the failure?

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The Durstenfeld algorithm is pretty simple, but I noted two things in your code. The random number you generate - that should have a range of 0 <= k <= SIZE-1 where a[SIZE];

    So the +1 on this line (#52 above), appears dodgy:
    Code:
    k = rand() % (j+1);
    Did rand() % j not work well?

    Similarly, line 49 appears to work well with (you are using different variable names), but have >= 0.
    Code:
    for(i=SIZE-1;i>0;i--) {
          j=rand() % i;
    Which you don't need - when you get to the last number, it has to go over to the permutation side (although it doesn't move), since it's the only number left.
    Last edited by Adak; 12-20-2012 at 05:54 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C program to find inverses of a permutation
    By newbie123 in forum C Programming
    Replies: 6
    Last Post: 08-22-2010, 07:17 AM
  2. Replies: 14
    Last Post: 02-07-2010, 12:38 PM
  3. Replies: 5
    Last Post: 08-14-2007, 10:34 AM
  4. Help with Permutation
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 07-06-2005, 11:13 PM
  5. permutation
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 09-01-2001, 04:13 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