arrays - 如何创建 n 个随机长度的字符串，其总和等于给定的数量？

Question

我正在尝试创建一种算法来创建随机长度的 n 字符串，其总和等于给定的数量。

一个更清楚的例子:

total = 20;
n = 7;

strings = ['aaaa', 'a', 'aaaaaaa', 'aa', 'aaa', 'aa', 'a'];

所以我有 7 个随机长度的字符串，它们各自长度的总和是(除非我计算错误)20。

直到现在我想出了这个递归函数:

gaps = [];
function createGapsArray(total, n) {
    if (n == 1) {
        var gapLength = total;
    } else {
        var gapLength = getRandomInt(1, total / 2);
    }

  var gap = "";
  for (var i = 0; i < gapLength; i++) {
    gap += "a";
  }
  gaps.push(gap);

  if (n > 1 && total > 0) {
    createGapsArray(total - gapLength, --n);
  }
}

这实际上行不通。通常它会在生成我想要的所有 n 段之前完成。通过我所做的一些测试，似乎将总数除以 4 而不是 2 就可以完成工作。喜欢:

var gapLength = getRandomInt(1, total / 4);

但是这个约束的选择是任意的。我想知道是否有更好的方法。

此外，我知道通过我的方法，算法可能会在开始时生成较长的段，在最后生成较小的段。我不介意均匀分布，但这没什么大不了的，因为对于我需要的，我可以在完成后简单地洗牌数组。

Answer 1

这个问题类似于“找到一个随机集合的k个数字，其总和为N”。这个答案的原始版本使用了一个简单的解决方案，如果数字是连续的(即 float )，该解决方案是无偏的:生成 [0, N] 范围内的 k-1 个数字，对它们进行排序，将 0在开头和结尾的 N，然后找出连续元素之间的差异。但是由于没有小数字符，我们需要数字是整数并且上述算法对包含 0 的集合有偏见(在连续情况下得到 0 的概率无穷小，但在离散情况下很重要)。

生成非空整数解的无偏解是在 [1, N-1] 范围内找到整数的随机 (k-1) 组合。要找到随机组合，请使用范围随机洗牌的前 k-1 个元素(使用 Fisher-Yates 洗牌)。然后对组合进行排序(如有必要)并在前面加上 0；这些值是每个字符串的起始位置(以便下一个值是结束位置。)

这不会产生空子串，因为每个子串都有一个唯一的起点。要包含空子字符串，请使用上面的 N+k 而不是 N，然后将每个范围缩小 1:如果索引已排序，您可以通过从 i 中减去 i 来实现^th 索引。

在 Python 中:

from random import sample
def random_split(str, k):
    v = [0] + sorted(sample(range(1, len(str)), k-1)) + [len(str)]
    return [str[v[i]:v[i+1]] for i in range(k)]

def random_split_allow_empty(str, k):
    v = [0] + sorted(sample(range(1, len(str)+k), k-1)) + [len(str)+k]
        return [str[v[i]-i:v[i+1]-i-1] for i in range(k)]

在 Javascript 中:

function shuffle(vec, k) {
  for (let i = 0; i < k; ++i) {
    let r = i + Math.floor(Math.random() * (vec.length - i));
    let t = vec[r];
    vec[r] = vec[i];
    vec[i] = t;
  }
  return vec;
}

function random_partition(N, k) {
  let v = [];
  for (let i = 1; i < N; ++i) v[i-1] = i;
  shuffle(v, k - 1);
  v[k-1] = 0;
  return v.slice(0, k).sort((a,b)=>a-b);
}

function random_split(s, k) {
  return random_partition(s.length, k).map(
    (v, i, a) => s.slice(v, a[i+1]));
}

function random_split_allow_empty(s, k) {
  return random_partition(s.length + k, k).map((v,i)=>v-i).map(
    (v, i, a) => s.slice(v, a[i+1]));
}