Skip to content

Instantly share code, notes, and snippets.

@therightstuff
Last active March 28, 2020 12:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save therightstuff/a1399a192aae85397452755a73898a4e to your computer and use it in GitHub Desktop.
Save therightstuff/a1399a192aae85397452755a73898a4e to your computer and use it in GitHub Desktop.
A list shuffle method that ensures every item is consumed
/*
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