如何获取bitarray的所有排列

本文关键字：排列 bitarray 何获取 获取 | 更新日期: 2023-09-27 18:28:15

如何为n大小的位数组生成所有排列？

我的意思是，例如，如果1和0的数组是整数类型，我可以像这个一样

for (int i = 0; i <= ~(-1 << n); i++)
   string s = Convert.ToString(i, 2).PadLeft(n, '0');

并且s将包含一些排列，例如101010或100000等等。所以我可以得到所有的排列。例如，对于n=3

000
001
010
011
100
101
110
111

但是如何对bitarray执行同样的操作呢？（因为我需要XOR运算等）

如何获取bitarray的所有排列

我现在还没有打开VS，但您可以使用BitArray(byte[])构造函数。

for (var i = 0; i < 1 << n; i++)
{
    byte[] bytes = BitConverter.GetBytes(i);
    var bitArray = new BitArray(bytes);
}

您必须进行实验，并提出将int转换为字节的移位逻辑。

如果您需要大于32/64位，那么您显然需要另一种方法。

为什么不使用int或long，因为在合理的时间内，您永远无法处理大于~2^32（实际上要小得多）的排列。

for (int i = 0; i < 64; i++)
{
        Console.WriteLine(Convert.ToString(i,2).PadLeft(6,'0'));
}

输出：

000000
000001
000010
000011
000100
000101
000110
000111
001000
001001
001010
001011
001100
etc.

这是基于我为最近的一个项目编写的递归列表填充过程。

private void GenerateStringsRecursive(List<string> strings, int n, string cur)
{
    if (cur.Length == n)
    {
        strings.Add(cur);
    }
    else
    {
        GenerateStringsRecursive(strings, n, cur + "0");
        GenerateStringsRecursive(strings, n, cur + "1");
    }
}

这样称呼它：

List<string> strings = new List<string>();
GenerateStringsRecursive(strings, n, "");
foreach (string s in strings)
{
    Console.WriteLine(s);
}

我想这将受到优化，例如使用StringBuilder等。

一个通用的Permute函数，它将返回任何可枚举对象的所有组合。

    public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> list)
    {
        for (int i = (1 << list.Count()) - 1; i >= 0; i--)
            yield return list.BitWhere(i);
    }
    public static IEnumerable<T> BitWhere<T>(this IEnumerable<T> list, int selector)
    {
        BitVector32 bits = new BitVector32(selector);
        int c = list.Count();
        for (int i = 1; i <= c; i++)
        {
            if (bits[1 << (c - i)])
                yield return list.ElementAt(i - 1);
        }
    }

您可以使用BigInteger执行此任务。它本质上是一个具有算术运算的位数组，因此您可以通过加一来排列位，就像您已经可以使用Int32和Int64整数一样。

同时，BigInteger支持位算法，因此您可以使用^运算符进行异或运算。

相关文章：