Shuffling an array, solved. Shuffle the songs! (Solution for an extra challange from the "Build a Library" project.)

Hello, I have been working on this, and 2 related topics in this forum seemed like they are not giving the solution. So, I just wanted to share my code for my coder friends who are looking for a solution to shuffle their array.

So, the project is this : Build A Library

Challenge is this : Create a method called shuffle for the CD class. The method returns a randomly sorted array of all the songs in the songs property.

My solution is this:

  shuffle () {
const index = []; 
const songList = this._songs; 
const shuffledSongs = []; 

for (let i= Math.floor(Math.random()* songList.length); index.length<songList.length;
     i=Math.floor(Math.random()*songList.length)) {
  if (!index.includes(i)){
  index.push(i);
  } else {i=Math.floor(Math.random()*songList.length)}
}

const shuffler = (arr,shuf) => {
for (let j = 0; j<songList.length; j++)
  shuffledSongs[j]=arr[shuf[j]]
}

shuffler(songList,index);
return shuffledSongs;
  }

Note: Sorry for any problems in my code, in advance. And I appreciate any improvements.

3 Likes

Thank you for this! I could not figure this one out for the life of me after hours of google and trying on my own.

1 Like

So what did you come up with to shuffle the song array?

@dugong-s @ashmariebeck @mtf

Here’s a simpler and more concise shuffle method, which I’ve based on a solution to a task I found on this JavaScript tutorial website:
https://javascript.info/task/shuffle
(click on solution and scroll down to the second half where there is a solution based on the Fischer-Yates shuffle algorithm) :nerd_face:

shuffle() {
  for (let i = this.songs.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [this.songs[i], this.songs[j]] = [this.songs[j], this.songs[i]];
  }
}

// assumes that the following getter is also used in the CD class:
 get songs() {
    return this._songs;
  }  

It works by:

  • iterating backwards through the songs array using a for() loop;

  • and then swapping each element with one of the preceding ones, selected at random.

I think it’s pretty neat! :stuck_out_tongue_winking_eye:

1 Like

Cool! Only problem I foresee is that the original track order is modified. Can we do this shuffle without affecting the stored data?

1 Like

Good point! I think @dugong-s addresses this in his code. I’ll take a further look and see if I can merge the best of both…

Are you referring to this line?

I was thinking more of these lines:

But, I haven’t looked at his solution in enough detail yet to decide if I’ll adapt my code for something along those lines, or something different. I just noticed that his code aims to return a separate array. I’m gonna refuel before attacking it :wink:

Ah, yes. A new array is returned, and the original remains unchanged. That is the goal to reach toward. Your own code can do this without much fuss.

const tracks = this.songs.slice()    // note the getter

That creates a standalone copy of the songs array. Now we we can manipulate that list and not affect the original.

Here is your code whittled down…

Swap method
  shuffle () {
    let t = tracks = this.songs.slice(); 
    let i, j, k = t.length;
    for (i = k; i > 0; i--) {
      j = Math.floor(Math.random() * k);
        [t[i-1], t[j]] = [t[j], t[i-1]];
    }
    return tracks;
  }
Random selection push method
  shuffle () {
    let s = this.songs;
    let k, n = s.length
    let tracks = [];
    while (tracks.length < n) {
      k = Math.floor(Math.random() * n);
      if (tracks.indexOf(s[k]) < 0) {
        tracks.push(s[k]);
      }
    }
    return tracks;
  }
shuffle() {
  const shuffledSongs = this.songs.slice();
  for (let i = shuffledSongs.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [shuffledSongs[i], shuffledSongs[j]] = [shuffledSongs[j], shuffledSongs[i]];
  }
  return shuffledSongs;
}

console.log(songInstance.songs);      // logs original, unshuffled song list
console.log(songInstance.shuffle());  // logs shuffled song list  
1 Like

I know you’re fond of analyzing things so let’s compare your swap method with the one above. First I’ll whittle it down so they have a closer visual match.

Note that assignments are right to left.

t = totally_long_name = ...

We use the totally long name for verbosity and self-documentation. It only needs to appear once in the code in that form. After that we can use the symbol which takes the value of the verbose variable. Since it represents a data structure in this case, both long name and symbol refer to the same object. The symbol is ideal for code representation. Repetitive verbosity is a distraction, imho. Once it is known what the symbol represents I have no issue running that through my mind, rather than repeating the verbose name. Sand flows throw a funnel better than clay.

shuffle() {
  let s = shuffledSongs = this.songs.slice();
  for (let i = s.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [s[i], s[j]] = [s[j], s[i]];
  }
  return shuffledSongs;
}

Nothing is changed but for the added symbol, s. If we forget what that means, we just look up a couple of lines, or down to the return statement. Easily doing without long names during the processing stage.

  shuffle () {
    let t = tracks = this.songs.slice(); 
    let i, j, k = t.length;
    for (i = k; i > 0; i--) {
      j = Math.floor(Math.random() * k);
        [t[i-1], t[j]] = [t[j], t[i-1]];
    }
    return tracks;
  }

Their similarities are easy to spot, as are the differences. How do both programs achieve the same result, only with slight difference?

1 Like

Great illustrations, thanks!
I didn’t know about these extra techniques for making our code more concise :+1:

So, I can see that by doing the following we can cut out repetion and overuse of long names:

  • Using a symbol to represent long names:
    e.g.
    s for shuffledSongs
    t for tracks

  • Defining empty variables with let at the outset to avoid having to use/repeat the keywords const and let later on in the function body:
    e.g.
    let i, j;

  • Where we use the same “value expression” more than once, we can achieve further conciseness by assigning this to a variable at the outset:
    e.g.
    let k = t.length;
    This results in the other small differences between our versions, namely the different use and position of +1's and -1's.

  • By using commas we can define the variables, to be assigned or referenced later in the function body, even more concisely, and avoid further repetition of the keywords let and const:
    e.g.
    let i, j, k = t.length;

However, just a couple of questions and a problem that this has thrown up for me:

  1. Is this symbol, we are talking about and using, the additional primitive data type which the course hasn’t covered yet? So far, I’ve covered the other five (number, string, null, boolean, undefined).

  2. In your for() statement, the initializer is set to start the iteration at an index value (t.length) which is one higher than the actual index value of the array’s last element (t.length - 1). Does this still work, because any initializer higher than the array’s actual last index value will just default to the last index value anyway?

  3. When I amend my shuffle() method (within my CD class) for the improvements in your version, and then run the code for a particular CD instance, I get the following error:

My amended shuffle() method (to include your suggested improvements):

shuffle() {
  let s = shuffledSongs = this.songs.slice();  // line that produces error
  let i, j, k = s.length;
  for (i = k; i > 0; i--) {
    j = Math.floor(Math.random() * k);
    [s[i-1], s[j]] = [s[j], s[i-1]];
  }
  return shuffledSongs;
}

console.log(cdInstance.shuffle());
// ReferenceError: shuffledSongs is not defined at CD.shuffle

// This modification (to the line that produces the error) corrects this:
const shuffledSongs = this.songs.slice();
const s = shuffledSongs;

How do I merge these two lines of code into one, like you did, but without getting an error? Maybe it’s because I don’t understand enough about how symbol works yet…


I’ve also just realised that we can make the code even more concise, by removing the k variable altogether, and merging it with the i variable, as follows:

shuffle() {
  let s = shuffledSongs = this.songs.slice();  // line that produces error
  let j, i = s.length; // i also takes on the replaced k variable's role 
  for (i; i > 0; i--) { // i now also does k's job, so no need for "i = k"
    j = Math.floor(Math.random() * i); // k replaced by i
    [s[i-1], s[j]] = [s[j], s[i-1]];
  }
  return shuffledSongs;
}

What do you think?


*** UPDATE ***

I’ve now come up with an equally succinct version, but which:

  1. does away with the need to use -1's in the final expression of the for() statement;

  2. sets the for() statement’s initializer to the index value of the actual last array element;

both of which I think make the overall code clearer and more readable…

shuffle() {
  let s = shuffledSongs = this.songs.slice();  // line that produces error
  let j, i = s.length - 1; // i reduced -1; now i = index of last element 
  for (i; i > 0; i--) {
    j = Math.floor(Math.random() * (i + 1)); // i must be increased +1 here 
    [s[i], s[j]] = [s[j], s[i]]; // now no need for [i-1] i.e. just [i]
  }
  return shuffledSongs;
}

The overall use of -1's and +1's is the same (i.e. twice); but personally, I prefer not to have them in the final expression in the for() statement as I think it makes its meaning clearer… do you agree?

2 Likes

Thank you for sharing this.it’s amazing :slight_smile:

Not a new type, no. The term ‘symbol’ is only used to set the short form of the name apart from the long form. ‘Stand-in’ would be a more accurate term. Perhaps not the best choice of word, under the circumstances.

Notice that in the critical statement (the swap) we use i - 1. In so doing, i does not exceed the range, and can still equal to zero at some point. It also saves us manipulating the value of i in two places to make the loop and random number work.

The error you get is not so easy to explain, though you do have a proper solution to that.

array = [1,2,3,4,5,6,7,8,9];
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
t = tracks = array.slice()
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
t
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
tracks
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]

The above doesn’t help explain the error, though.

s = shuffledSongs = array.slice()
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
s
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
shuffledSongs
(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]

It may be that chained assignments are not supported in all browsers? I did have my doubts, but didn’t test in Edge/IE browsers, only Chrome and FF. When in doubt, one supposes we should stick to tried and proven methods that won’t surprise us with errors. Not a problem. Just so we know that the shortened name refers to the same array as the longer name.

It may appear to work, yes, but the value of i is diminishing so has a smaller random solution set with each successive iteration. k on the other hand is constant so we always have the same size solution set. I’d stick with the k in the code.

I’d hate to think I’m suggesting something that is not a best practice. While JS does permit multiple variables in a single declaration, it is a practice one should use judiciously, in cases where it is obvious what the variables will be used for. Were it a longer program, the variables might be better declared separately.

You might recall how I once stated that verbosity is something we can avoid by having it at one end of a transaction, but not at both. Above we clearly describe what our data structure is, but in the code we use the symbol in its place. The other variables are purely utility and have no need of documentation. To my mind it makes the code much easier to follow. None of the meaning is lost, though, as we can see by the return value.

All in all, be sure to look up best practices and use good reason to stray from the straight and narrow. Let the situation dictate the practice in use. If it creates confusion, then stick to the style guide recommendations.

1 Like

When we ''shuffle" a playlist of songs, do we really want to hear them in any random order, or do we have other requirements? For example, what if we don’t want to hear any songs in the order they normally play on the CD? (ie. song 5 shouldn’t come right after song 4.) What if we don’t want to hear the first song first, or the last song last, or the 5th song 5th, etc.? Just some thoughts to consider. I came up with a shuffle function that meets the extra requirements I mentioned. Let me know what you think :slightly_smiling_face:

//Song Shuffler
//Rules: 1. No song can follow the song it normally follows.
//       2. No song may remain in it's original position ie. first can't
//          be first, last can't be last, fifth can't be fifth, etc.
//       3. Simply reversing the order is unacceptable unless there are only 2 or 3 songs
//          since reversing the order is the only way to meet the first 2 rules with 2 songs
//          songs, and only rule 1 or 2 can be followed with 3 songs.
const shuffle = (songList) => {
  const songs = songList.slice();
  let randomIndexArray = [];
  let shuffledSongs = [];
  let failedCount;
  let startOver = false;
  switch(songs.length) {
    case 0:
    case 1:
      return songs;
    case 2:
    case 3:
      shuffledSongs = songs;
      return shuffledSongs.reverse(); //only way to satisfy requirements - see rule 3
    default:
      while(randomIndexArray.length <= songs.length) { 
        if(randomIndexArray.length === songs.length) {
          randomIndexArray.forEach(i => shuffledSongs.push(songs[i]));
          if(shuffledSongs.join() === songs.reverse().join()) { //check for rule 3 violation
            shuffledSongs = [];
            songs.reverse();
          } else {
            return shuffledSongs;
          }
        }
        const randomNumber = Math.floor(Math.random() * songs.length);
        if(!randomIndexArray.includes(randomNumber) //don't want the same song twice
          && randomNumber != randomIndexArray.length //rule 2
          && randomNumber != randomIndexArray[randomIndexArray.length - 1] + 1) { //rule 1
          randomIndexArray.push(randomNumber);
          failedCount = 0;
        } else {
          failedCount++;
        }
        if(failedCount > songs.length * 2) { //after double the array length of failures to follow the rules, remove the last index and try again
          randomIndexArray.pop();
          failedCount = 0;
          startOver = !startOver
          if(startOver) { //after failing double the array length times for a second time, start over from the beginning
            randomIndexArray = [];
            startOver = !startOver;
          }
        }
      }
  }
}

//Test using numbers to ensure rule 1 compliance
const mySongs = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20"];
for (let c = 1; c <= 10; c++) { //change 10 to 100, 1000, or even 10000000 if you like
  console.log(`Shuffled: ${shuffle(mySongs).join(',')}`);
}
console.log(`My Songs: ${mySongs}`);

Output:

Shuffled: 3,11,20,5,17,9,16,15,10,6,14,18,8,2,19,13,7,4,12,1
Shuffled: 2,15,10,8,14,9,6,16,19,3,1,18,17,11,20,12,5,7,4,13
Shuffled: 3,10,16,15,1,14,18,11,4,20,13,17,12,2,5,8,6,9,7,19
Shuffled: 14,12,20,13,18,8,4,3,1,9,6,11,5,19,16,2,10,17,7,15
Shuffled: 20,13,16,18,9,4,10,6,17,15,1,19,8,7,14,5,11,3,2,12
Shuffled: 13,20,12,1,17,7,15,2,6,18,10,16,9,4,19,14,5,11,8,3
Shuffled: 19,12,5,2,16,18,14,20,4,13,10,7,1,8,11,15,6,3,17,9
Shuffled: 18,13,4,16,7,9,1,12,5,19,14,10,15,6,11,17,2,20,8,3
Shuffled: 8,17,9,12,18,14,13,4,20,5,2,19,16,3,10,7,6,1,11,15
Shuffled: 15,12,9,3,13,20,18,7,17,6,14,4,8,19,11,1,16,2,10,5
My Songs: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 //original order

So essentially what we want to do is perform a shuffle of indices and then compare them to the stock index. If any elements line up with the stock index, then swap with one of the adjacent elements. Doesn’t really seem that ominous a task and the logic should be fairly simple.

// build a stock index
stock_index = [];
for (let x = 0; x < songs.length; x++) {
    stock_index.push(x);
}
// shuffle
s = stock_index;
k, n = s.length;
t = [];
while (t.length < n) {
    k = Math.floor(Math.random() * n);
    if (t.indexOf(s[k]) < 0) {
        t.push(s[k]);
    }
}
// now compare the two indexes
for (x = 1, x < s.length; x++) {
    if (t[x-1] === s[x-1]) {
        t[x-1], t[x] = t[x], t[x-1];
    }
}
// now compile the track list
tracks = [];
t.forEach(x => tracks.push(song[x])

Of course, this is theoretical and probably has a flaw. It strikes me as simpler and a once only operation.

I ran your code on pythontutor.com with a sample array of 5 elements, and got the following:

[ '1', '2', '3', '4', '5' ] //original order
[ '4', '1', '3', '5', '2' ]
[ '4', '5', '3', '1', '2' ]
[ '4', '2', '3', '5', '1' ]
[ '4', '2', '3', '1', '5' ]

So, song 3 remained 3rd each time, song 2 remained 2nd twice, song 5 appeared 5th once,
song 5 follows 4 once, song 2 follows 1 once, song 3 follows 2 twice. The songs are indeed
shuffled from their original order, but the extra conditions I suggested are not met. Obviously one’s definition of shuffled doesn’t have to meet mine. Just throwing out food for thought.

A few moments later …
Just ran it again for kicks, and logged this:

[ '3', '4', '5', '2', '1' ]
[ '5', '2', '4', '3', '1' ]
[ '1', '2', '3', '4', '5' ] //randomly generated the original order
[ '5', '1', '2', '4', '3' ]
[ '3', '1', '2', '5', '4' ]

This actually illustrates a significant point regarding random. In a truly random scenario, the original order is just as likely as any other order combination. :wink:

1 Like

Thanks for road testing the idea. It occurred to me that swapping with a neighboring element only satisfies that one condition, and probably creates anomalies further down the line. You’ve proven that.

Loved that one.

Hair-brained ideas are the starting point of a lot of cool solutions, so I won’t stop being brash, especially if this leads to a simple solution, or defaults to a brute force, repetitive one, which won’t take a lot of logic, just lots of iterations.

let s = stock_index;
let k, t, n = s.length;
do {
    let flag = true;
    t = [];
    while (t.length < n) {
        k = Math.floor(Math.random() * n);
        if (t.indexOf(s[k]) < 0) {
            t.push(s[k]);
        }
    }
    for (let x = 0, x < s.length; x++) {
        if (t[x] === s[x]) {
            flag = false;
            break;
        }
    }
    if (flag) break;
} while (true)
trackList = [];
t.forEach(x => trackList.push(songs[x]))

Once again, theoretical. It just keeps generating new sequences until no elements match the stock array. This is probably the simplest way to do it. Mind since I try not to over think, I tend to under think. There are trade-offs.

I understand the shuffle algorithm I’m using as only swapping with a random index value that precedes the one currently being iterated over. Once a swap has occurred and the iteration moves “down one” (to i--), I don’t see any reason to shuffle these elements further. In this scenario, the “pool” our random number is being generated from reduces in parallel with “i” so I think it’s ok to do away with “k” and just use “i” instead.

Does that make sense?

It does, yes.

 > class Media {
     constructor() {
       this.songs = [1,2,3,4,5,6,7,8,9,10,11,12]
     }
     shuffle() {
       let s = this.songs.slice();
       let j, i = s.length - 1;
       for (i; i > 0; i--) {
         j = Math.floor(Math.random() * (i + 1));
         [s[i], s[j]] = [s[j], s[i]];
       }
       return s;
     }
   }
<- undefined
 > album = new Media()
<- Media {songs: Array(12)}
 > album.songs
<- (12) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
 > album.shuffle()
<- (12) [6, 5, 7, 2, 12, 1, 11, 3, 4, 8, 10, 9]
 > album.shuffle()
<- (12) [10, 1, 6, 2, 11, 3, 8, 12, 4, 7, 5, 9]
 > album.shuffle()
<- (12) [7, 5, 4, 6, 1, 2, 10, 9, 11, 8, 3, 12]
 > album.shuffle()
<- (12) [8, 3, 12, 1, 11, 6, 4, 10, 9, 7, 2, 5]
 > album.songs
<- (12) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
1 Like