The basic idea is: figure out how many 1s and 2s we want, calculate how many consecutive "runs" of each we need (i.e. 1111222211 is two runs of 1s and one run of 2s), then calculate how long each run will be with some random partitioning. Please note that the partitioning is slightly biased. Randomly dividing a number n into k positive integers is a very hard problem, but this should be decently random depending on your application.
Please let me know if you want me to explain any part of this code better!
function getRandomInt(min, max) {
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
function count_switches(arr) {
let switches = 0;
let last = arr[0];
for (let i = 1; i < arr.length; ++i) {
if (arr[i] != last) {
switches += 1;
last = arr[i];
}
}
return switches;
}
function generate_partitions(total, splits) {
while(true) {
let randoms = [];
for (let _ = 0; _ < splits; _++) {
randoms.push(Math.random());
}
let randoms_sum = randoms.reduce((a, b) => a + b, 0)
for (let i = 0; i < splits; ++i) {
randoms[i] = Math.floor((randoms[i] / randoms_sum) * total)
}
randoms_sum = randoms.reduce((a, b) => a + b, 0)
for (let _ = 0; _ < total - randoms_sum; ++_) {
if (randoms.includes(0)) {
randoms[randoms.indexOf(0)]++;
} else {
randoms[getRandomInt(0, splits - 1)]++;
}
}
if (!randoms.includes(0)) {
shuffleArray(randoms);
return randoms;
}
}
}
function generate_splits(vec_length, num_splits) {
let num_ones = 0, num_twos = 0;
while(true) {
num_ones = getRandomInt(0, vec_length);
num_twos = vec_length - num_ones;
if (Math.min(num_ones, num_twos) * 2 >= num_splits) {
break;
}
}
let num_one_runs = Math.floor((num_splits + 1) / 2);
let num_two_runs = num_one_runs;
if (num_splits % 2 == 0) {
if (Math.random() > .5) {
num_one_runs += 1;
} else {
num_two_runs += 1;
}
}
let one_run_partitions = generate_partitions(num_ones, num_one_runs), two_run_partitions = generate_partitions(num_twos, num_two_runs)
let first = one_run_partitions, first_output = 1
let second = two_run_partitions, second_output = 2
if (one_run_partitions.length < two_run_partitions.length || (one_run_partitions.length == two_run_partitions.length && Math.random() > .5)) {
first = two_run_partitions, first_output = 2
second = one_run_partitions, second_output = 1
}
const output = []
for (let i = 0; i < Math.max(num_one_runs, num_two_runs); ++i) {
for (let _ = 0; _ < first[i]; ++_) {
output.push(first_output);
}
if (i < second.length) {
for (let _ = 0; _ < second[i]; ++_) {
output.push(second_output);
}
}
}
return output;
}
let output = generate_splits(480, 160);
console.log(output, count_switches(output));
Example of heavily biased outputs with 380 1's, 100 2's, and 160 switches. Runtime was 0m0.045s:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1]