3

I have been asked for an assignment to use FisherYates shuffle on an array to be taken in from a file (that, I managed to do) using functions.

 int FisherYates(int *player, int n) { //implementation of Fisher                 
     int i, j, tmp; // create local variables to hold values for shuffle

     for (i = n - 1; i > 0; i--) { // for loop to shuffle
         j = rand(); //randomise j for shuffle with Fisher Yates
         tmp = player[j];
         player[j] = player[i];
         player[i] = tmp;
     }
     return player;
}

It basically just needs to shuffle the list of players and return me the output so I can print it out in main().

I would very much appreciate it if anyone could show me how to modify the code to make it work, since with this version, I get a error at compile time: 

 invalid conversion from 'int*' to 'int' [-fpermissive]
chqrlie
  • 131,814
  • 10
  • 121
  • 189
Lorenzo Battilocchi
  • 862
  • 1
  • 10
  • 26
  • To get help, you'll have to describe what's wrong with your code. For example, you "get quite a few errors at compile time", but you don't describe what those errors are or what you tried to do to fix them. It looks also like your algorithm is wrong: you want to pick a random number between 0 and i (inclusive) to swap element i with, but your random number is in the range 0...RAND_MAX. You also don't need to apologize and explain yourself -- just a well-written question is enough. http://stackoverflow.com/tour is a good read for how to use the site. – Paul Hankin Feb 18 '17 at 22:43
  • 1
    At what line does the error occur? Also, you probably don't want to return `player`: it's already changed since it's a pointer, no need to return it. –  Feb 18 '17 at 22:59
  • 1
    @Evert in fact, that's probably the source of the error since `player` is not an `int`, but rather an `int*`. – pjs Feb 18 '17 at 23:00
  • 2
    You're going to want to constrain the range of the random value. It has to be a valid index for your array. – pjs Feb 18 '17 at 23:01
  • @pjs that is my suspicion as well, in which case the error occurs elsewhere, hence my question about the line. As such, the question at the moment has not enough information. –  Feb 18 '17 at 23:09
  • @Evert the compiler should note that the return type of the function is `int` but the return statement is for `int*`. Totally agree that Lorenzo should supply the full diagnostics. – pjs Feb 18 '17 at 23:14
  • Note that `rand()` returns a number in the range 0..RAND_MAX, but most of those values are well outside the range of 0..n-1 that are valid array accesses. – Jonathan Leffler Feb 18 '17 at 23:19
  • You should take a look at [Is this C implementation of Fisher-Yates shuffle correct?](http://stackoverflow.com/a/3348142) And maybe the commentary (links) available in the README.md at [https://github.com/jleffler/soq/tree/master/src/so-0612-7503](https://github.com/jleffler/soq/tree/master/src/so-0612-7503). – Jonathan Leffler Feb 18 '17 at 23:24
  • @Evert yes the error occurs when I am returning. How could I modify the code so that the int* becomes an int? Thank you very much again! – Lorenzo Battilocchi Feb 18 '17 at 23:45
  • @LorenzoBattilocchi Why do you want to return an `int` at all? – melpomene Feb 18 '17 at 23:59
  • @LorenzoBattilocchi You should go the other way - the return type should be `int*` if you want to return the array (actually a pointer to the array). You don't need to return anything, though, since you're shuffling the array in-place. It will be shuffled after the function is done, regardless of whether you supply a return value. – pjs Feb 18 '17 at 23:59
  • That looks like a C++ error, not C. Are you sure you know what language you're using? – melpomene Feb 19 '17 at 00:00

2 Answers2

4

You already have the result in player, so returning void should work.

Reference for Fisher-Yates

void FisherYates(int *player, int n) { //implementation of Fisher
     int i, j, tmp; // create local variables to hold values for shuffle

     for (i = n - 1; i > 0; i--) { // for loop to shuffle
         j = rand() % (i + 1); //randomise j for shuffle with Fisher Yates
         tmp = player[j];
         player[j] = player[i];
         player[i] = tmp;
     }
}
Community
  • 1
  • 1
Tectrendz
  • 1,354
  • 2
  • 17
  • 36
  • `rand() % n` isn't correct -- `rand() % (i + 1)` is. Your code will produce a random shuffle, but not a uniformly distributed one (even if you assume `rand` is a good random number generator). – Paul Hankin Feb 18 '17 at 23:57
  • @PaulHankin: do you mind expanding on your remark for us not so savvy random programmers? – chqrlie Feb 19 '17 at 00:38
  • @chqrlie Because this is how the algorithm works? The point is that `a[i]` is swapped with `a[0..i]` (thus no swap is a possibility), not with `a[0..n-1]`. – HolyBlackCat Feb 19 '17 at 00:53
  • @chqrlie Wikipedia explains: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm and https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Implementation_errors – Paul Hankin Feb 19 '17 at 00:55
  • 1
    @Tectrendz I assume that was a typo (since your own link says that it's `% (i + 1)`), so I decided to edit it. – HolyBlackCat Feb 19 '17 at 00:58
0

Two quick things about your function:

  1. rand() requires that srand(...) be called to seed the number generator.

    ... srand(clock());

    for (i=n-1; i>0; i--){ // for loop to shuffle j = rand()%n; //randomise j for shuffle with Fisher Yates ...

  2. int FisherYates(int *player, int n) is prototyped to return an int, but you are returning pointer to int Options are to do as Tectrendz suggested and just change the prototype to return void (since player is returned in the arguments), or change the function to return an int *. But this would be redundant because (int *player,... allows the value to be returned via the argument.

ryyker
  • 22,849
  • 3
  • 43
  • 87