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. Popular pages Recent additions arrays, permutation 