2

假设您有一个任意大的二维数组，其中包含偶数个项目。为清楚起见，我们还假设您只能在两个事物之间进行选择，以将其作为给定项目放入数组中。您将如何在数组中的给定索引处放置一个随机选择，但是一旦数组被填充，您将在两个选择之间进行平均分配？

如果有任何代码答案，Java 是首选，但其他语言也可以。

4

5 回答 5

1

您基本上可以以相反的方式考虑它。您可以从数组中选择 n/2 个元素并将第一个值放入其中，而不是决定给定索引，将哪个值放入其中。然后将第二个值放在另一个 n/2 中。

于 2012-09-02T01:21:03.147 回答
1

二维A[M,N]数组可以映射到向量V[M*N]（您可以使用行优先或列优先顺序进行映射）。

从一个向量开始V[M*N]。用第一个选择填充它的前半部分，用第二个选择对象填充数组的后半部分。运行Fisher-Yates洗牌，并将洗牌后的数组转换为二维数组。数组现在填充了在两个选项之间平均分配的元素，并且每个特定索引处的选项都是随机的。

于 2012-09-02T01:27:29.940 回答
0

下面创建矩阵区域的大小，并用第一个选项 ( )List<T>填充一半，用第二个选项 ( ) 填充一半。之后，它应用 shuffle（即 Fisher-Yates，via ）并开始用这些值填充矩阵。spaces[0]spaces[1]Collections.shuffle

static <T> void fill(final T[][] matrix, final T... space) {
  final int w = matrix.length;
  final int h = matrix[0].length;
  final int area = w * h;
  final List<T> sample = new ArrayList<T>(area);
  final int half = area >> 1;
  sample.addAll(Collections.nCopies(half, space[0]));
  sample.addAll(Collections.nCopies(half, space[1]));
  Collections.shuffle(sample);
  final Iterator<T> cursor = sample.iterator();
  for (int x = w - 1; x >= 0; --x) {
    final T[] column = matrix[x];
    for (int y = h - 1; y >= 0; --y) {
      column[y] = cursor.next();
    }
  }
}
于 2012-09-02T01:36:38.483 回答
0

伪代码：

int trues_remaining = size / 2;
int falses_remaining = size / 2;

while (trues_remaining + falses_remaining > 0)
{
  if (trues_remaining > 0)
  {
    if (falses_remaining > 0)
      array.push(getRandomBool());
    else
      array.push(true);
  }
  else
    array.push(false);
}

但是，实际上并不能扩展到两个以上的值。怎么样：

assoc_array = { 1 = 4, 2 = 4, 3 = 4, 4 = 4 };

while (! assoc_array.isEmpty())
{
  int index = rand(assoc_array.getNumberOfKeys());
  int n = assoc_array.getKeyAtIndex(index);

  array.push(n);

  assoc_array[n]--;
  if (assoc_array[n] <= 0) assoc_array.deleteKey(n);
}

编辑：刚刚注意到你要求一个二维数组。好吧，将这种方法应用于 n 维应该很容易。

EDIT2：根据您上面的评论，“校园选择”是一个很棒的名字。

于 2012-09-02T01:43:02.023 回答
0

听起来您对随机性的要求不是很严格，但我想我会为任何可能从中受益的人贡献更多想法。

您基本上是在要求一个伪随机二进制序列，而我所知道的最流行的是最大长度序列。这使用了一个 n 位寄存器和一个线性反馈移位寄存器来定义具有完全平坦频谱的周期性系列 1 和 0。至少它在某些范围内是完全平坦的，由序列的周期（2^n-1 位）确定。

这意味着什么？基本上，这意味着如果使用其全长，则可以保证序列在所有班次（以及因此频率）上是最大随机的。与从随机数生成器生成的等长数字序列相比，它的每个长度包含比典型随机生成的序列更多的随机性。

正是由于这个原因，它被用于确定系统白噪声分析中的脉冲函数，特别是当实验时间很宝贵且高阶交叉效应不太重要时。因为序列相对于自身的所有变化是随机的，所以它的自相关是一个完美的 delta 函数（除了上面指出的限定符），因此刺激不会污染刺激和响应之间的互相关。

我真的不知道你对这个矩阵的应用是什么，但如果它只是需要“出现”随机，那么这将非常有效地做到这一点。就平衡而言，1 与 0，序列保证恰好比 0 多一个 1。因此，如果您尝试创建 2^n 的网格，则可以保证通过添加一个0 到最后。

So an m-sequence is more random than anything you'll generate using a random number generator and it has a defined number of 0's and 1's. However, it doesn't allow for unqualified generation of 2d matrices of arbitrary size - only those where the total number of elements in the grid is a power of 2.

于 2012-09-02T02:25:10.520 回答