在 Javascript 中打乱向量，直到有一定数量的非重复元素？

问题描述 投票：0回答：3

我有一个随机生成的 1 和 2 向量，我想不断地重新洗牌，直到我有一定数量的“开关”。例如，如果 vec = [1, 1, 1, 2, 1, 2, 1]，则有四个“开关”（与前一个元素不匹配的元素，忽略向量中的第一个元素）。我想重新洗牌这个向量，直到我有，比如说，恰好三个开关。

现在，我正在使用 while 循环，通过嵌入的 for 循环来计算开关数量（循环遍历向量中的每个元素，检查该元素是否等于前一个元素，如果不等于则增加计数器）一旦计数器达到适当的值，while 循环就会终止。这可行，但效率确实很低——运行可能需要几分钟（使用完整向量 = 480 个元素，目标是 160 个开关）。

任何关于更有效地编码的建议将不胜感激！预先非常感谢。

javascript random vector
3个回答
0
投票

编辑：我最初花了很长时间思考这个问题的解决方案，但老实说我的解决方案非常hacky。这是一个更干净、更好的解决方案，以更准确的方式进行随机分区

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!');

基本思想是：找出我们想要多少个 

1
和 
2
，计算我们需要的每个连续“运行”次数（即 1111222211 是两次运行 
1
和运行一次 
2
s），然后通过一些随机分区计算每次运行的时间。请注意，分区略有偏差。将数字 
n
随机划分为 
k
正整数是一个非常困难的问题，但这应该是相当随机的，具体取决于您的应用程序。

如果您希望我更好地解释此代码的任何部分，请告诉我！

    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));

具有 380 个 1、100 个 2 和 160 个开关的重偏置输出示例。运行时间是

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]
0
投票

您可以获取所需的开关数量，生成开关的索引数组，例如

                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

并用值填充数组。

检查结果并在必要时重复。

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));

0
投票

您可以将开关视为随机长度的相同值元素的序列。然后你的向量作为这些开关的总和。

换句话说，如果你想要 

S
开关，你需要将向量分割为 
S + 1
随机长度部分，并相应地用 
1
或 
2
填充这些部分。

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

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

  const Vector = Array.from(Array(V).keys());

  // setting random switch points on the vector
  for (let i = 0; i < S; ++i) {
    const r = Math.random() * (V - i - 2) + i + 1 | 0;
    [Vector[i], Vector[r]] = [Vector[r], Vector[i]];
  }  
  const switchPoints = Vector.slice(0, S).sort((a, b) => b - a);
  
  let state = Math.random() > .5; // initial switch state
  let p = switchPoints.pop();
  Vector.forEach((e, i, a) => {
    if (i === p) {
      state = !state;
      p = switchPoints.pop();
    }
    a[i] = 1 + state;
  });
  return Vector;
}

console.log(JSON.stringify(f(4, 1)))
console.log(JSON.stringify(f(5, 5)))
console.log(JSON.stringify(f(480, 160)))
console.log(JSON.stringify(f(48000, 16000)))
.as-console-wrapper { max-height: 100% !important; top: 0; overflow:auto !important}

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.