reorganizing a series of 19 bytes into every single combination of any length

Question

There are these 19 bytes (I am looking for combinations not the number of combinations)

17 00 00 00 A4 EA DB 13 02 00 00 00 00 00 00 A3 D3 02 CC

I need any possible unique combination which matches these "rules":

• at least 4 bytes long

• the order of the bytes can't change(so 17 A3 D3 02 CC is ok but A3 D3 02 CC 17 isn't, because in the original string 17 was at the being but A3 D3 02 CC was at the end)

Let me try giving you examples of possible combinations:

17 00 00 00 A4 EA DB 13 02 00 00 00 00 00 00 A3 D3 02

17 00 00 00 A4 EA DB 13 02 00 00 00 00 00 00 A3 D3

17 00 00 00 A4 EA DB 13 02 00 00 00 00 00 00 A3

all the way to 17 00 00 00

17 A3 D3 02 CC

17 00 A3 D3 02 CC

00 A3 D3 02 CC

17 A4 02 CC

See the bytes stay in the same order for example the first byte 17 can only in the first byte's place

I don't want combination like

A4 17 02 CC

Because now 17 has changed order compared to A4

Answer 1

The basic idea, as others have mentioned, is to use a bit mask of 19 bits and calculate for each number which bytes from the original list should be included.

Here's a C# program that prints all 2^19 possibilities. As before, it does not take into account duplicates:

namespace ConsoleApplication2 {
    using System;

    class Program {
        private static int[] sourceBytes = { 0x17, 0x00, 0x00, 0x00, 0xA4, 0xEA, 0xDB, 0x13, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xA3, 0xD3, 0x02, 0xCC };

        private static bool IsBitSet(int n, int bit) {
            int mask = 1 << bit;
            return ((n & mask) == mask);
        }

        private static int NumberOfBits(int n) {
            int sum = 0;
            while (n > 0) {
                if ((n & 1) == 1) {
                    sum++;
                }
                n >>= 1;
            }
            return sum;
        }

        static void Main(string[] args) {
            for (int i = 524288 - 1; i >= 0; i--) { // 524,288 = 2^19
                if (NumberOfBits(i) >= 4) {
                    // Add the bytes from the list that are in the current bit mask
                    for (int bit = 0; bit < sourceBytes.Length; bit++) {
                        if (IsBitSet(i, bit)) {
                            Console.Write(sourceBytes[bit]);
                            Console.Write(' ');
                        }
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}

Answer 2

Basically, you're asking for a binary number of length (23*8) == 184 bits. I believe there are more such numbers than there are atoms in the universe! The number of combinations is 2 ** (23 * 8).

To think about why this is, simply realize that this is a simple lottery, where numbers are allowed to repeat. You pick one number for the first byte, and that can be between 0 and 255 (256 options). Then you pick a number for the second byte, and that can be between 0 and 255, so you have (256 * 256) options. Then you pick a number for the third byte, and that can be between 0 and 255, so you have (256 * 256 * 256) options (which is 16 million at this point, with 20 bytes to go...)

The fact that you also allow shorter numbers does add a little more to the 2 ** 184 number of possible byte arrangements, but not enough that it substantially changes the tractability of the problem.

Answer 3

The most important part of the question is that the order of the bytes cannot change.

Let's start with a first simplified problem:

1. Assume that each number is distinct. (Obviously false)
2. Assume that you there is no lower limit to the number of choices (also obviously false)

Then you have a simple choice for each number: Should I include this number or not? (The order is already given.) For this simplified problem, you only have 2¹⁹=524288 possibilities. That would take a while to print out, but it's small enough to compute.

Removing either simplification leaves you with FEWER possibilities.

So, let's remove the first simplification. When you are looking at a unique number, you have two choices: either to put that number in your combination, or to leave it out. When you are looking at a sequence of n 00s, you have n+1 choices: put no 00s into the combination, put one 00 in the combination, ..., put n 00s in the combination.

Therefore, at this point you have 2 * 4 * 2⁵ * 7 * 2⁴ = 28672 choices.

I leave it to you to figure out how many of these choices have 3 bytes or fewer.

Answer 4

I think this is what you are looking for:

Module Module1

    Sub Main()
        Dim bytes() As Byte = {&H17, &H0, &H0, &H0, &HA4, &HEA, &HDB, &H13, &H2, &H0, &H0, &H0, &H0, &H0, &H0, &HA3, &HD3, &H2, &HCC}

        Combine(New Byte() {}, bytes)
    End Sub

    Sub Combine(ByVal sequence() As Byte, ByVal pool() As Byte)
        '   test current sequence
        If Test(sequence) Then
            Console.Write("Found sequence: ")
            For Each b As Byte In sequence
                Console.Write("{0:X2} ", b)
            Next
            Console.WriteLine()
        End If

        '   done if pool is empty
        If pool.Length = 0 Then
            Return
        End If

        '   recurse adding next byte from the pool
        Dim newSequence(sequence.Length) As Byte
        Array.Copy(sequence, newSequence, sequence.Length)
        newSequence(sequence.Length) = pool(0)
        Dim newPool(pool.Length - 2) As Byte
        Array.Copy(pool, 1, newPool, 0, pool.Length - 1)
        Combine(newSequence, newPool)

        '   recurse without adding next byte from the pool
        Combine(sequence, newPool)
    End Sub

    Function Test(ByVal sequence() As Byte) As Boolean
        '   the test function that you haven't provided goes here

        '   this example returns True if the sequence is 4 bytes or more, causing every combination of at least 4 bytes to be printed
        If (sequence.Length >= 4) Then
            Test = True
        Else
            Test = False
        End If
    End Function

End Module

I leave the implementation of the Test function to you as you didn't provide that in the original question. My implementation basically treats all sequences of 4 bytes or more as passing the test, so it prints all combinations.

I used a recursive algorithm that starts with an empty sequence and all 19 of your bytes in a "pool" of bytes. I then recurse both by moving the first byte of the pool into the sequence I'm building, then by ignoring the first byte of the pool altogether.