how to get all permutations for bitarray

Question

how to generate all permutations for bitarray of n size?

I mean for example if array of 1 and 0 has integer type I can do like this

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

and s will contain some permutation for example 101010 or 100000 and etc. So I can get all permutations. For example for n=3

But how to do the same for bitarray?(because I need XOR operations and etc.)

A permutation is an ordering of a set (usually the set 1, 2, ... n). So 100000 and 101010 can't be permutations of the same set. What do you really mean when you use the word permutation? — Adam Mihalcin, Mar 19 '12 at 23:45
What is a 'permutation'? It seems your definition deviates somewhat from the normal definition. Could you please explain the question better? — Kendall Frey, Mar 19 '12 at 23:47
I think the OP means all possible unique sequences of bits that fit within a given bit length. — Drew Noakes, Mar 19 '12 at 23:54
@АртёмЦарионов Is there an upper limit on `n`? There are 4 billion possible bit arrays of 32 bits, which will cause your process to run out of memory unless it's running as a 64-bit process. — Adam Mihalcin, Mar 19 '12 at 23:59
the no upper limit but I think it will be no more than 7 or 8 — Артём Царионов, Mar 20 '12 at 00:05

Drew Noakes · Answer 1 · 2012-03-22T18:55:37.590

3

I don't have VS open right now, but you could use the BitArray(byte[]) constructor.

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

You'll have to experiment and come up with the shifting logic to convert an int into bytes.

If you need greater than 32/64 bits, then you'll obviously need another approach.

edited Mar 22 '12 at 18:55

answered Mar 19 '12 at 23:57

Drew Noakes

300,895
165
679
742

cannot resolve symbol IntToBytes. Or IntToBytes - my own method for converting?and It should return array of bytes? – Артём Царионов Mar 20 '12 at 00:02
1

`IntToBytes` has been implemented: `BitConverter.GetBytes(int)`. http://msdn.microsoft.com/en-us/library/de8fssa4.aspx – Kendall Frey Mar 20 '12 at 00:06
1

`BitConverter.GetBytes` is a method which converts an `int` into a `byte[]`. As always be careful about endianness with this method. (What order the `byte`s are in) – Guvante Mar 20 '12 at 00:07

L.B · Answer 2 · 2012-03-20T00:10:01.410

2

Why don't you work with int or long , since you will never able to work with permutations larger than ~2^32(in fact much lesser) in a reasonable time.

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

Output:

edited Mar 20 '12 at 00:10

answered Mar 20 '12 at 00:00

L.B

114,136
19
178
224

score 1 · Answer 3 · answered Mar 20 '12 at 00:04

This is based on a recursive list-filling procedure that I wrote for a recent project.

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");
    }
}

Call it like this:

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

I imagine this would be subject to optimizations such as using a StringBuilder etc.

score 1 · Answer 4 · answered Mar 20 '12 at 00:05

A generalised Permute function that will return all the combinations of any enumerable.

    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);
        }
    }

score 0 · Answer 5 · answered Oct 17 '21 at 12:22

You can use BigInteger for this task. It is essentially a bit array with arithmetic operations, so you can permute the bits by adding one, as you already can do with Int32 and Int64 integers.

At the same time, BigInteger supports bit arithmetics, so you can do xor with ^ operator.

how to get all permutations for bitarray

5 Answers5

Linked