Shuffling an Array with Fisher Yates

[raven maple]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[torpid cypress]

I don't understand what you mean by "but a number can only be outputted after 5 other numbers had passed", could you give examples and explain that?

What does "passed" mean in this context as well?

[meager bobcat]

I think he means:

he want to create a new array of size 2*initial_size, whose elements are made up of the first one, with 2 repetition for each element, and shuffled
(not especially create a new array; but print it)

with the extra constraint 2 equal elements must be separated by 5 other elements

is that so @granite lily ?

[granite lily]

After the array is passed through the function the order of the array would be 1 4 5 10 3 9 7 11 1 2 12 6 9 8 11 4 12 5 6 7 2 10 8 3. You can see the numbers are shuffled and no number shows up twice until 5 other numbers have been output.

[granite lily]

Yes exactly thats perfect.

[torpid cypress]

Are you looking for help coming up with the answer, or on how to write the answer in C, or both?

[granite lily]

Both please.

[torpid cypress]

So I don't know the answer, nor would I want to straight-up give it to you, but I can give you a bit of my reasoning behind what must be done when I read the question

Or at least how I'd approach it, but it may be dumb because it'd be too slow for large arrays

[granite lily]

Maximum array size would be 12

[torpid cypress]

Cool

Try to guess what my dumb, brute-force suggestion might be

[granite lily]

I have no idea Ive been at this for days 😅

Also I used numbers to just make it easier to explain the array would contain words

[torpid cypress]

Numbers and words are the same, yeah

So the hint to my idea is: once you've created the array, the only constraint is that 2 equal elements must be separated by 5 other elements. Assuming that your program is allowed to take an infinite amount of time, you can use this to your advantage if this is your only constraint your program needs to worry about

I know that in practice you want your program to finish relatively quickly, but knowing this solution is important anyways, even if you don't use it

[granite lily]

Yeah

[torpid cypress]

Here's the dumbest approach that I can think of, but that could absolutely work:
https://en.wikipedia.org/wiki/Bogosort?wprov=sfla1

You just generate a random array, and check if it satisfies your one constraint you have

[meager bobcat]

I feel like the following idea might also be worth the trial:

Let L be the initial size of the array. Let N be a co-prime with 2L such that

(1*N)%(2L) != 1
(2*N)%(2L) != 1
...
(5*N)%(2L) != 1

then (my guess, but I haven't proved it) we would have for all 0 <= M < 2L-1: (M+5N)%(2L) != M+1

consider the mapping f(i) = i/2 and process as follows:

element_to_print = initial_array[f(i * N)]

Example:

initial array is {1,2,3,...,8,9}
L=10, 2L = 20;
you can pick N=9 for example, since

 9 % 20 != 1
18 % 20 != 1
27 % 20 != 1
36 % 20 != 1
45 % 20 != 1

I think that would give a "psuedo-random" progression.

since your array is bounded by 12, it should be doable to precompute some valid N for all sizes

[granite lily]

I love the name.

[granite lily]

Thank you both ill try both out

[meager bobcat]

in python this yielded the progression:
[0, 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, 9, 4, 8, 3, 7, 2, 6, 1, 5]

(and I think the idea would also work if you start from a random point in the array. the same with N=3, starting at 7:

[3, 5, 6, 8, 9, 1, 2, 4, 5, 7, 8, 0, 1, 3, 4, 6, 7, 9, 0, 2]

[torpid cypress]

Another less dumb solution than bogosort is how one could write a sudoku solver, where you just put a digit in a cell, check whether that is valid according to the sudoku rules, and if not, you remove that digit from the cell and try another digit

Really insightful video explaining the idea:
https://youtu.be/G_UYXzGuqvM?si=_IL7DNBCxhlEgaGf

[granite lily]

The array can be less than 12, the array takes up to 12 songs(can take less if user chooses to).

[meager bobcat]

yes indeed; so that would still work

with my idea, you can either pre-compute an array of correct N that fits the constraints, and try a generic method to find a new one if ever the size becomes larger than 12

[raven maple]

@granite lily Has your question been resolved? If so, type !solved :)

[granite lily]

Okay im just trying to code it now

Its quite complicated

[meager bobcat]

just to make my idea more explicit, because maybe it wasn't clear enoug, here are small python snippets:

verify to check if N can be used for L (in the script, L is twice the size of the array)
progression moves the cursor

Example:

verify(17, 20) // -- True. 17 fits for a length of 10
progression(17, 20) // [3, 2, 0, 9, 7, 6, 4, 3, 1, 0, 8, 7, 5, 4, 2, 1, 9, 8, 6, 5]

[meager bobcat]

yeah and it's not truly "random".
you can randomize a bit my playing on the initial step (this can be chosen randomly) and the corresponding N (you could have a pool of 10 N (if any) for each sizes, and select randomly there. or else you try to recompute some N on the fly.

I suspect that for small sizes, you'll be good pre-computing a lot of them

for a human, it's likely random enough, though. after all, psuedo random generators work exactly like that... I just find one that also meets the constraint

[granite lily]

I was told to use the Fisher Yates Algorithm along with srand(time(NULL)); to randomise the array

[meager bobcat]

ah right! it's in the title 🤣

I forgot about that info

[granite lily]

I dont even know if its possible with those requirements

[meager bobcat]

I have no clear idea about that

[granite lily]

!format

[raven maple]

for (int i = 0; i < *playListSongs; i++) {
  int j = rand() % (i + 1);
  char swap[MAX_LENGTH];
  if (j != i) {
    // shuffle playlist
    strcpy(swap, playlist[i]);
    strcpy(playlist[i], playlist[j]);
    strcpy(playlist[j], swap);
  }

Amo

[granite lily]

This shuffles the 12 songs

[meager bobcat]

(aside note: you could work only with indices and copy only once the array elements at the very end)

[torpid cypress]

It isn't really clear what is meant by "use the Fisher Yates Algorithm", since you are being asked to do something that would require a modification of the Fisher-Yates shuffle

Kind of a ship of Theseus dilemma

[loud abyss]

Can there be duplicates?

Or are the elements always {1 .. n}?

[granite lily]

Sorted list of songs:
Lorde

• Green Light
• Tennis Court
• The Louvre
  Taylor Swift
• Anti-Hero
• Bad Blood
• Shake it Off
  The Cranberries
• In the End
• Salvation
• Zombie
  U2
• Beautiful Day
• One
• With or Without you

3. Create a random playlist of the songs given as input ensuring that the same song can only appear again after at list 5 different other songs have played. The same song must appear twice. For example, this is a possible output for the list of artists/group names and songs provided at step 2.

Shuffled Playlist:
Lorde - Green Light
The Cranberries - Zombie
The Cranberries - In the End
Taylor Swift - Bad Blood
Taylor Swift - Shake it Off
U2 - One
Lorde - Green Light
U2 - With or Without you
The Cranberries - Salvation
Taylor Swift - Anti-Hero
U2 - Beautiful Day
Taylor Swift - Bad Blood
The Cranberries - In the End
Taylor Swift - Shake it Off
U2 - One
Lorde – Tennis Court
The Cranberries – Salvation
Lorde - The Louvre
The Cranberries - Zombie
Taylor Swift - Anti-Hero
U2 - Beautiful Day
Lorde – Tennis Court
U2 - With or Without you
Lorde - The Louvre

[loud abyss]

Basically all unique

An idea that's way less random but works on the first try:

• Make a copy of the array a, call it b or something
• Shuffle a
• Look at the last 5 elements of a, call these xs. Remove them from b
• Shuffle b then concat b to a
• Shuffle xs then concat xs to a

[meager bobcat]

doesn't sound like it will work for length=6 😬

[loud abyss]

This algo will "miss" some possible outputs(in the sense that it will never generate it, even though it's valid), but the upside is it works first try and isn't too complicated

[loud abyss]

true, needs more tweaking

[meager bobcat]

idk actually

ah yes I see why

indeed

[granite lily]

How was this a beginner task 😭

[meager bobcat]

it's a funny problem

[loud abyss]

Did they specify "how random" your algo must be? (idk what that's supposed to mean either)

Like a very obvious way to do this is to just shuffle the array, then append a copy of the shuffled array to itself

Feels kinda cheaty though?

[granite lily]

Thats what i did then realised in the example output one of the songs appears twice within the first 12 songs

[meager bobcat]

I'm not even sure what kind of randomness does a RPNG satisfies tbh.. (when the seed is random and uniform:) each element is uniform, that sounds about right. maybe we have pairwise independence. but independence as a whole, I'm pretty sure we don't have that

[loud abyss]

Hmm... what about this

• Make a copy of the array a, call it b
• Shuffle a
• Look at the last 5 elements of a, call these xs. Remove them from b
• For the first 5 elements of b, after appending b_i to a, insert xs_i into b at a random position
• Append the rest of b to a

Though this doesn't exactly sound beginner considering you're in C

[torpid cypress]

I'd personally still consider it Fisher-Yates if your version still achieves the answer by putting a random element at the end, using a swap. So the technique in this video would still totally be viable, would be relatively fast, and can't ever fail to produce a correct answer, if there is one.

[meager bobcat]

what if you'd do something like:

implement Fisher-Yates but at every step,
toss a coin and decide whether or not you continue, or else you re-inject an element that has been injected 5 elements or more earlier
(1/2 change to continue the regular algo, 1/2 to pick at random an element in [injection_cursor++, current_size-5], something like that)

something like that

that will be my last contribution 😄 hahaha ; have to go now; glhf 👋

[meager bobcat]

@granite lily lol, I had wayyy too much fun implementing my proposition in C (don(t just copy-paste; + it does not follow your f-y requirement)

#include <stdio.h>
#include <stdlib.h>


const static unsigned int PRIMES[] = {37,31,29,23,19,17,13,11,7,5,3};


static _Bool verify(unsigned int length, unsigned int n)
{
    const unsigned int range = 2*length;
    {
        if(range > n ? (range % n) : (n % range)) {
            unsigned int cursor = n;
            for(int i = 0; i < 5; i++) {
                if(cursor % range == 1) {
                    goto abort;
                } else {
                    cursor += n;
                }
            }
            return 1;
        } else {
            goto abort;
        }
    }
    abort: {
        return 0;
    }
}

static unsigned int find_candidate(unsigned int length)
{
    for(unsigned int i = 0; i < sizeof(PRIMES)/sizeof(*PRIMES); i++) {
        if(verify(length, PRIMES[i])) {
            return PRIMES[i];
        }
    }
    /*
     * Note: giving up. sorry not sorry
     */
    return 61;
}

unsigned int choose_seed(unsigned int length)
{
    /*
     * Generate a random seed instead, and get for free a PRNG.
     * The below heuristic is good enough for me right now.
     */
    return length/3*2;
}


int main()
{
    const unsigned int indices[] = {0,1,2,3,4,5,6,7,8,9,10,11,12};
    const unsigned int length = sizeof(indices)/sizeof(*indices);

    const unsigned int n = find_candidate(length);
    const unsigned int s = choose_seed(length);

    for(unsigned int i = 0; i < 2*length; i++) {
        const unsigned int index = ((s + n*i) % (2*length)) / 2;
        printf("%d, ", indices[index]);
    }
}

Prints

4, 9, 2, 7, 0, 5, 11, 3, 9, 1, 7, 12, 5, 10, 3, 8, 1, 6, 12, 4, 10, 2, 8, 0, 6, 11

[granite lily]

I couldnt even copy and paste it my teacher would know straight away😅

I was thinking of making another array of size 5, when a song is shuffled its added as the first element in this array, next 4 more songs are shuffled and added. Fisher yates grabs a random song then places it at i and increments until the end of the array so this should work. At the same time a helper function uses strcmp to compare the next song the fisher yates algorithm chooses to the songs in the array of size 5. If it is inside fisher yates reshuffles and chooses another song then again sees if its inside the array of 5, if it isnt the song is added to the position of i in the shuffled area and the song replaces the first element of the array of size 5.

[meager bobcat]

have you tried this one? it looks similar

[granite lily]

yes thats where i got the inspiration from im just trying to make it now

[meager bobcat]

I didn't try to implement it but that sounds doable yes

and it explicitly uses fisher-yates

[granite lily]

this what i have so far

!format

[raven maple]

for (i = 0; i < totalSongs * 2; i++) {
  int j = rand() % (totalSongs * 2);
  char swap[MAX_LENGTH];

  while (!check(j, doubled)) {
    j = rand() % (totalSongs * 2);
  }

  // Update the shuffled playlist
  strcpy(swap, doubled[i]);
  strcpy(doubled[i], doubled[j]);
  strcpy(doubled[j], swap);
}

Amo

[granite lily]

my shuffling algorithm, doubled[] is the array with 24 songs

!format

[raven maple]

bool check(int j, char doubled[24][80]) {
  int max = j - 5;
  if (max < 0) {
    max = 0;
  }
  for (; max < j; max++) {
    if (strcmp(doubled[j], doubled[max]) == 0) {
      return false;
    }
  }
  return true;
}

Amo

[granite lily]

My helper function that checks if a song has showed up within the last 5 songs

It works sometimes but it has quite a few hiccups

[meager bobcat]

haha, love that last sentence

[granite lily]

My brain is fried

[granite lily]

what you think

[meager bobcat]

I think it's not so bad but I'm not sure: does it always work, or do you find bugs?

[granite lily]

It works then at the end they begin to not follow the 5 rule anymore