Using a combination of function generators and Set.
Working Example:
function randomNumber(max) {
return Math.floor(Math.random() * Math.floor(max));
}
function* uniquePair(max) {
const pairs = new Set();
const maxPairs = max * max;
while (true) {
const res = [randomNumber(max), randomNumber(max)];
const resStr = res.join(",");
switch (true) {
case !pairs.has(resStr):
pairs.add(resStr);
yield res;
break;
case pairs.size === maxPairs:
//done
return;
default:
console.log(resStr + " Exists...");
}
}
}
const gen10 = uniquePair(10);
const si = setInterval(function() {
const next = gen10.next();
if (next.done === true) {
clearInterval(si);
console.log("Done");
} else {
console.log(next.value);
}
}, 500);
.as-console-wrapper { max-height: 100% !important; top: 0; }
How does this work?
const gen = uniquePair(10);
This will create a new generator for the given max range.
function* uniquePair(max) {
const pairs = new Set();
const maxPairs = max * max;
/** more code **/
}
The first two lines are only created once. The pairs to memorise the unique combinations already created (empty at the start) and maxPairs to know the max possible unique combinations.
function* uniquePair(max) {
/** more code **/
while (true) {
const res = [randomNumber(max), randomNumber(max)];
const resStr = res.join(",");
/** more code **/
}
}
Here we create an infinite loop. Each loop we create a random combination of two values. We also create the string representation of those two values (ex: [1,0] -> "1,0").
function* uniquePair(max) {
/** more code **/
while (true) {
/** more code **/
switch (true) {
case !pairs.has(resStr):
pairs.add(resStr);
yield res;
break;
/** more code **/
}
}
}
For each iteration of the while loop, we check to see if the string representation of our two values exists within our set. If it doesn't, we add that string representation to the set and yield the array.
yield is where we temporarily "leave" our generator and send back the result, which is then accessible in:
const next = gen.next();
//next.value -> [1,0] , next.done -> false
function* uniquePair(max) {
/** more code **/
while (true) {
/** more code **/
switch (true) {
/** more code **/
case pairs.size === maxPairs:
//done
return;
/** more code **/
}
}
}
If the string representation of the values already exists within our set, we check to see if the set's size is equal to the max number of pairs. If it is, we can assume there are no more results possible and we simply return
At this point the generator is done and will no longer return any values:
const next = gen.next();
//next.value -> undefined , next.done -> true
function* uniquePair(max) {
/** more code **/
while (true) {
/** more code **/
switch (true) {
/** more code **/
default:
console.log(resStr + " Exists...");
}
}
}
If none of the previous cases match then we can assume that 1. The current combination already exists and 2. There are still combinations left. We then do the next loop iteration and come up with a new combination and start again till a new unique combination is found.
Multiple instances runnable:
This code also allows the ability to run multiple instances of a generator each having different max numbers.
const gen2 = uniquePair(2);
const gen4 = uniquePair(4);
const gen6 = uniquePair(6);
let cycle = 1;
const si = setInterval(function(){
console.log(`Cycle: ${cycle}`);
const next2 = gen2.next();
const next4 = gen4.next();
const next6 = gen6.next();
if(next2.done === false){
console.log(`2: [${next2.value.join(",")}]`);
} else {
console.log("2: DONE");
}
if(next4.done === false){
console.log(`4: [${next4.value.join(",")}]`);
} else {
console.log("4: DONE");
}
if(next6.done === false){
console.log(`6: [${next6.value.join(",")}]`);
} else {
console.log("6: DONE");
}
console.log("-------");
cycle++;
if(cycle === 40) clearInterval(si);
}, 1000);
function randomNumber(max){return Math.floor(Math.random()*Math.floor(max))}
function*uniquePair(max){const pairs=new Set();const maxPairs=max*max;while(!0){const res=[randomNumber(max),randomNumber(max)];const resStr=res.join(",");switch(!0){case!pairs.has(resStr):pairs.add(resStr);yield res;break;case pairs.size===maxPairs:return;}}}
.as-console-wrapper { max-height: 100% !important; top: 0; }
Min Max Solution:
function randomNumber(max,min) {
return Math.floor(Math.random() * (max - min) + min);
}
function* uniquePair(max, min = 0) {
const pairs = new Set();
const maxPairs = Math.pow(max-min, 2);
console.log(maxPairs);
while (true) {
const res = [randomNumber(max, min), randomNumber(max, min)];
const resStr = res.join(",");
switch (true) {
case !pairs.has(resStr):
pairs.add(resStr);
yield res;
break;
case pairs.size === maxPairs:
//done
return;
default:
console.log(resStr + " Exists...");
}
}
}
const gen10 = uniquePair(10,5);
const si = setInterval(function() {
const next = gen10.next();
if (next.done === true) {
clearInterval(si);
console.log("Done");
} else {
console.log(next.value);
}
}, 500);
Solution where all possibilities are pre-calculated:
The main issue with the main example I have is that, the more combinations requested the harder it'll be for the algo to find a unique pair. This is of course negligible if:
- There are less than a 100 pairs
- Only 60-70% of the possible matches are ever requested
If both the above points are false then this solution would be optimal:
function randomNumber(max) {
return Math.floor(Math.random() * Math.floor(max));
}
function generateAllPossibilities(max){
const res = [];
for(let i = 0; i < max; i++){
for(let j = 0; j < max; j++){
res.push([i,j]);
}
}
return res;
}
function* uniquePair(max) {
const pairs = generateAllPossibilities(max);
while (true) {
const len = pairs.length;
if(len === 0) return;
yield pairs.splice(randomNumber(len), 1).shift();
}
}
const gen10 = uniquePair(10);
const si = setInterval(function() {
const next = gen10.next();
if (next.done === true) {
clearInterval(si);
console.log("Done");
} else {
console.log(next.value);
}
}, 200);
.as-console-wrapper { max-height: 100% !important; top: 0; }
