来自整数数组的 C# 可能性树

Question

我如何使用 C# 从整数数组构建可能性树？如果在每一步都从数组中删除一个元素，我需要制作所有可能的数组变体。

例如，如果我们有来自三个整数 [1,2,3] 的数组，那么树应该如下所示：tree view

Answer 1

我会将其视为二进制算术问题：

static void Main(string[] args)
{
    int[] arr = { 1, 2, 3 };
    PickElements(0, arr);
}

static void PickElements<T>(int depth, T[] arr, int mask = -1)
{
    int bits = Math.Min(32, arr.Length);
    // keep just the bits from mask that are represented in arr
    mask &= ~(-1 << bits); 
    if (mask == 0) return;

    // UI: write the options
    for (int i = 0; i < depth; i++ )
        Console.Write('>'); // indent to depth
    for (int i = 0; i < arr.Length; i++)
    {
        if ((mask & (1 << i)) != 0)
        {
            Console.Write(' ');
            Console.Write(arr[i]);
        }
    }
    Console.WriteLine();

    // recurse, taking away one bit (naive and basic bit sweep)
    for (int i = 0; i < bits; i++)
    {
        // try and subtract each bit separately; if it
        // is different, recurse
        var childMask = mask & ~(1 << i);
        if (childMask != mask) PickElements(depth + 1, arr, childMask);
    }
}

对于 TreeView，只需将 Console.Write 等替换为节点创建，大概将父节点传入（和向下）作为递归的一部分（代替 depth ，也许）。

要了解它在做什么，请考虑二进制文件； -1 是：

11111111111111...111111111111111

然后我们查看bits，这是我们从数组长度中得出的，在这个例子中发现它是3。那么我们只需要看 3 位；该行：

~(-1 << bits)

为此计算掩码，因为：

-1          = 1111111....1111111111111
(-1 << 3)   = 1111111....1111111111000 (left-shift back-fills with 0)
~(-1 << 3)  = 0000000....0000000000111 (binary inverse)

然后我们将其应用于我们的输入掩码，因此我们只查看最低有效的 3 位，通过 mask &= ...。如果结果为零，我们运行无事可做，所以停止递归。

UI更新很简单；我们只扫描我们关心的 3 位，检查当前位是否是我们掩码的 "on"； 1 << i 创建一个仅包含 "i-th set bit" 的掩码； & 和 != 0 检查该位是否已设置。如果是，我们在输出中包含该元素。

最后，我们需要开始带走位，来看子树；我们可以可能对此更复杂，但我选择只扫描所有位并尝试它们 - 最坏的情况是每个级别 32 位测试，这没什么。和以前一样，1 << i 只创建了 "i-th set bit" 的掩码。这次我们要禁用那个位，所以我们 "negate" 和 "and" 通过 mask & ~(...)。有可能这个位 already 禁用了，所以 childMask != mask 检查确保我们只 actually 在我们禁用了位时递归之前已启用。

最终结果是，我们最终得到的掩码是连续的：

11..1111111111111111 (special case for first call; all set)
   110   (first bit disabled)
      100   (first and second bits disabled)
      010   (first and third bits disabled)
   101   (second bit disabled)
      100   (second and first bits disabled)
      001   (second and third bits disabled)
   011   (third bit disabled)
      010   (third and first bits disabled)
      001   (third and second bits disabled)

请注意，对于 更简单的 组合示例，可以只需在单个 for 中迭代，使用选择元素的位；然而，我用递归的方式完成了它，因为我们需要构建一个连续减法的树，而不仅仅是没有特定顺序的平坦可能性。

来自整数数组的 C# 可能性树

C# possibilities tree from integers array

c#

arrays

tree