Thread: Permutation program

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?

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?