Last active
March 28, 2020 12:56
-
-
Save therightstuff/a1399a192aae85397452755a73898a4e to your computer and use it in GitHub Desktop.
A list shuffle method that ensures every item is consumed
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Motivation: | |
A shuffler that ensures that no items in a list (a music playlist in particular) are left behind. | |
Mechanism: | |
When an item in the current shuffle group is used, it is moved to the next shuffle group and the next shuffle group is reshuffled. | |
Shuffling the current group doesn't affect the number of items remaining in the current shuffle group. | |
Drawback: | |
Shuffling the current group when there's only one item remaining will have no effect, the item must be consumed (to preserve fairness) and only then will be shuffled in to the next group | |
Performance: O(N) each time an item is consumed | |
Memory complexity: O(N) constructs an index array for each shuffle | |
*/ | |
let list = []; | |
function createItem(val){ | |
return { | |
val: val, | |
shuffleGroup: 1 | |
} | |
} | |
// retrieve next item and shuffle it into the following shuffle group | |
function shift() { | |
let item = list.shift(); | |
item.shuffleGroup++; | |
list.push(item); | |
// shuffling the next group could be performed asynchronously) | |
shuffle(item.shuffleGroup); | |
return item; | |
} | |
function printList() { | |
let output = '['; | |
for (let i in list) { | |
if (i > 0) output += ', '; | |
output += `${list[i].val} (${list[i].shuffleGroup})`; | |
} | |
console.log(`${output}]`); | |
} | |
// return random number between min and max inclusive | |
function randomInt(min, max) { | |
return min + Math.floor(((max + 1) - min) * Math.random()); | |
} | |
// shuffle the specied shuffle group, or the current group if none specified | |
function shuffle(shuffleGroup){ | |
shuffleGroup = shuffleGroup || list[0].shuffleGroup; | |
// create index list for specified shuffle group's items | |
let shuffler = []; | |
for (let i in list) { | |
if (list[i].shuffleGroup == shuffleGroup) { | |
shuffler.push({ | |
item: list[i], | |
index: i | |
}); | |
} | |
} | |
// fisher-yates in-place shuffle, if used for music playlist should take other aspects | |
// into consideration (see https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/ ) | |
let len = shuffler.length - 1; | |
for (let i = 0; i < len; i++){ | |
let target = randomInt(i + 1, len); | |
swap(shuffler[i].index, shuffler[target].index); | |
} | |
} | |
function swap(a, b) { | |
let tmp = list[a]; | |
list[a] = list[b]; | |
list[b] = tmp; | |
} | |
// initialize list | |
for (let i = 1; i < 11; i++){ | |
list.push(createItem(i)); | |
} | |
console.log('initial state'); | |
printList(); | |
console.log('first shuffle'); | |
shuffle(); | |
printList(); | |
console.log('playing list'); | |
for (let i = 0; i < 5; i++) { | |
let item = shift(); | |
console.log(`playing ${item.val}`) | |
printList(); | |
} | |
console.log('mid-play shuffle'); | |
shuffle(); | |
printList(); | |
console.log('resume playing list'); | |
for (let i = 0; i < 10; i++) { | |
let item = shift(); | |
console.log(`playing ${item.val}`) | |
printList(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment