Created
August 13, 2020 08:31
-
-
Save RP-3/c3edc9200e107a2734049fc0a5320edc to your computer and use it in GitHub Desktop.
This file contains hidden or 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
var CombinationIterator = function(characters, combinationLength) { | |
this.storage = characters.split(''); | |
this.hasMore = combinationLength <= characters.length; | |
this.ptrs = new Array(combinationLength).fill(0).map((_, i) => i); | |
}; | |
CombinationIterator.prototype.resetAfter = function(i){ | |
let nextIndex = this.ptrs[i] + 1; | |
for(let j = i+1; j<this.ptrs.length; j++){ | |
if(nextIndex >= this.storage.length) return false; | |
this.ptrs[j] = nextIndex++; | |
} | |
return true; | |
} | |
CombinationIterator.prototype.next = function() { | |
// fetch the latest result | |
const result = this.ptrs.map((cIndex) => this.storage[cIndex]).join(''); | |
// get the next combination ready | |
let nextAvailable = false; | |
for(let i=this.ptrs.length-1; i>=0; i--){ | |
this.ptrs[i]++; // increment this ptr | |
// check for collisions and OOB | |
if(this.ptrs[i] >= this.storage.length || this.ptrs[i] === this.ptrs[i+1]){ | |
this.ptrs[i]--; // backtrack | |
continue; // and try the next pointer | |
} | |
// success! | |
if(this.resetAfter(i)) nextAvailable = true; // reset all the trailing pointers | |
break; // and stop! | |
} | |
if(!nextAvailable) this.hasMore = false; // if we failed, remember that fact | |
return result; | |
}; | |
CombinationIterator.prototype.hasNext = function() { | |
return this.hasMore; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment