# Permutation program

• 12-17-2012
C_Nik
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; }```
• 12-17-2012
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
• 12-17-2012
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?
• 12-17-2012
Click_here
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
• 12-17-2012
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.
• 12-17-2012
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.
• 12-18-2012
C_Nik
Ok Thanks Adak! I'm going to check this out. Learning something new everyday! I appreciate this!
• 12-19-2012
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...

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; }```
• 12-19-2012
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?
• 12-19-2012
AndiPersti
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
• 12-20-2012
C_Nik
@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-20-2012
Can you post up a simple example of it with the table, that shows the failure?
• 12-20-2012
`k = rand() % (j+1);`
```for(i=SIZE-1;i>0;i--) {       j=rand() % i;```