Shuffling a vector in Javascript until there are a set number of nonrepeating elements?-CodePudding

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.

CodePudding user response：

You could take the wanted count of switches, generate an array of indices for the switches, like

                v  v  v  v  v
indices   0  1  2  3  4  5  6
values   [1, 1, 1, 2, 1, 2, 1]
switches    0  0  1  1  1  1
indices           2  3  4  5
fill1           1  2  1  2  1
fill2           2  1  2  1  2

and fill the array with values.

The check the result and repeat, if necessary.

function disperse(a, b, switches) {
    const
        count = c => v => c[v]--,
        size = a   b - 1;

    do {
        const indices = new Set;
            
        while (indices.size < switches) indices.add(Math.floor(Math.random() * size));

        let value = Math.floor(Math.random() * 2)   1;

        const result = Array.from(
            { length: a   b },
            (_, i) => indices.has(i - 1)
                ? (value = { 1: 2, 2: 1 }[value])
                : value
        );
        if (result.every(count({ 1: a, 2: b }))) return result;
    } while (true);
    return [];
}

console.log(...disperse(5, 3, 4));

CodePudding user response：

You might consider a switch as a sequence of same-value elements of a random length. Then your vector as a sum of those switches:

const f = (V, S) => {
  // V - vector length
  // S - number of switches

  if (V - S <= 0) return 'Vector cannot fit all the switches';

  const result = [];
  let state = Math.random() > .5|0, // initial switch state
      Vrest = V;
  while (result.length < V) {
    const switchLength = S ? Math.random() * (Vrest - S--)   1|0 : Vrest;
    for (let i = 0; i < switchLength;   i) result.push(1   state);
    Vrest -= switchLength;
    state = !state;
  }

  return result;
}

console.log(JSON.stringify(f(4, 1)))
console.log(JSON.stringify(f(5, 5)))
console.log(JSON.stringify(f(480, 160)))

.as-console-wrapper { max-height: 100% !important; top: 0; }

CodePudding user response：

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]