有没有办法随机选择数组的一个元素，但前提是该元素通过某个测试？

Question

我有一个二维布尔数组，例如

bool[,] array = new bool[,] {
  { false, false, true},
  { true, false, false},
};

我想选择一个随机元素即

false

并将其切换为

true

。我一直在四处寻找，似乎无法找到一种方法来不包括随机选择中的

true

元素。

我不太熟悉所有的术语，所以我可能只是错过了一个明显的解决方案。

我知道可以随机选择一个元素，检查它是否为假，如果不是则再试一次，直到所选元素为假，但这可能会在大数组中重复几次非常少

 false

元素。

Answer 1

也许这个例子会让你开始。

internal class Program
{
    static void Main(string[] args)
    {
        var rand = new Random(new Guid().GetHashCode());

        var myArray = new[]
        {
            new Thing() { IsSet = false},
            new Thing() { IsSet = false},
            new Thing() { IsSet = true},
            new Thing() { IsSet = true},
            new Thing() { IsSet = false},
        };

        var trues = myArray.Where((thing) => thing.IsSet).ToArray();
        var randomSelection = trues[rand.Next(0, trues .Length)];
    }
}

class Thing
{
    public Guid Id { get; set; } = Guid.NewGuid();
    public bool IsSet { get; set; }
}

基本上，首先使用

Where

将您的结果过滤到您想要随机选择的结果，然后从这些结果中执行随机选择。

Answer 2

要解决一般情况的问题，我们首先要找到随机索引；我们 可以借助水库采样:

// Either random index within source
// or -1 if source is empty
public static int RandomIndex<T>(IEnumerable<T> source, 
                                 Func<T, bool> selector = default, 
                                 Random random = default) {
  if (source is null)
    throw new ArgumentNullException(nameof(source));
  if (selector is null)
    selector = item => true;

  random ??= Random.Shared;

  int result = -1;
  int index = -1;
  int count = 0;

  foreach (var item in source) {
    index += 1;

    if (selector(item))
      if (random.Next(++count) == 0)
        result = index;
  }

  return result; 
}

然后有一个

bool[,]

数组

bool[,] array = new bool[,] {
  { false, false, true},
  { true, false, false},
};

我们可以找到随机索引，如果有效则应用它：

int index = RandomIndex<bool>(array.Cast<bool>(), item => !item);

if (index >= 0)
  array[index / array.GetLength(1), index % array.GetLength(1)] = true;

请注意，解决方案只需要扫描一次数组（

O(n * m)

时间复杂度）并且不创建任何集合（

O(1)

空间复杂度）

小提琴