I have a randomly generated vector of 1s and 2s, which I want to continuously reshuffle until I have a set number of 'switches'. For example, if vec = [1, 1, 1, 2, 1, 2, 1], then there are four 'switches' (elements that don't match the previous element, discounting the first element in the vector). I want to reshuffle this vector until I have, say, exactly three switches.
Right now, I'm using a while loop that counts the number of switches via an embedded for loop (which cycles through each element in the vector, checking whether that element is equal to the previous element, and incrementing the counter if not) The while loop terminates once the counter hits the appropriate value. This works, but it's really inefficient -- it can take several minutes to run (using a full vector = 480 elements, aiming for exactly 160 switches).
Any advice re: coding this more efficiently would be greatly appreciated!! Thanks very much in advance.
Edit: I spent a long time thinking of a solution to this problem originally but honestly my solution was very hacky. Here is a much cleaner and far better solution that does the random partitions more accurately, and is guaranteed to terminate (which the other technically isn't.)
function get_random_int(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function count_switches(arr) {
let switches = 0;
let prev = arr[0];
for (let i = 1; i < arr.length; ++i) {
switches += arr[i] != prev;
prev = arr[i];
}
return switches;
}
function generate_partitions(total, splits) {
if (splits > total) return [];
const split_arr = Array(splits + 1).fill(1);
for (let i = 0; i < total - splits; i++) {
split_arr[get_random_int(0, splits)]++;
}
return split_arr;
}
function generate_splits(vec_length, num_splits) {
const partitions = generate_partitions(vec_length, num_splits);
const splits = [];
let curr_val = get_random_int(1, 2);
partitions.forEach((partition) => {
splits.push(...Array(partition).fill(curr_val));
curr_val = 3 - curr_val;
});
return splits;
}
let output = generate_splits(480, 160);
console.log(output, count_switches(output), 'switches counted!');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]