1. ## 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;
}```

2. 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. 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. 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

5. 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. 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.

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

8. 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. 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. 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

11. @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. Can you post up a simple example of it with the table, that shows the failure?

13. 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.