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?

Quote:

---

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.

Quote:

---

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?

Quote:

---

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.