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

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

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?

Originally Posted by C_Nik

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

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.

Originally Posted by C_Nik

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.

Ok Thanks Adak! I'm going to check this out. Learning something new everyday! I appreciate this!

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

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?

Originally Posted by C_Nik

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

@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

Can you post up a simple example of it with the table, that shows the failure?

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.