0

有这 19 个字节（我正在寻找组合而不是组合的数量）

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

我需要与这些“规则”相匹配的任何可能的独特组合：

  • 至少 4 个字节长

  • 字节的顺序不能改变（所以17 A3 D3 02 CC 可以，但 A3 D3 02 CC 17不是，因为在原始字符串中，17 是在，但 A3 D3 02 CC 在最后）

让我试着给你一些可能组合的例子：

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

一直到 17 00 00 00

17 A3 D3 02 CC

17 00 A3 D3 02 CC

00 A3 D3 02 CC

17 A4 02 CC

查看字节保持相同的顺序，例如第一个字节17只能在第一个字节的位置

我不想要像这样的组合

A4 17 02 CC

因为现在17相比于改变了顺序A4

4

5 回答 5

3

正如其他人所提到的，基本思想是使用 19 位的位掩码，并为每个数字计算应包含原始列表中的哪些字节。

这是一个打印所有 2^19 可能性的 C# 程序。和以前一样，它不考虑重复：

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();
                }
            }
        }
    }
}
于 2009-12-31T22:26:15.583 回答
1

我想我终于明白了这个问题：

你有 19 件物品，你想知道如果你拿，你能做出多少组合

  • 一次 4 个
  • 一次 5 个
  • ...
  • 一次 19 个。

一次取m的n 个项目的组合数称为“ n选择m ”，计算公式为：

             ！_
    ——————
    （米！）（n-米）！

因此，您需要为从 4 到 19的所有m值添加（19 选择m ）。

您可以通过注意以下几点来简化计算：

     n选择m   =   n选择 ( n - m )

因此，您可以计算从m = 4 到m = 9 的组合，将其加倍以计算m = 10 到m = 15，然后将m = 15 到 19 的组合相加。

这是一个用于计算的 bash shell 脚本，在大约四分之一秒的计算后给出523128的答案：

# Calculate the factorial of $1.
fact()
{
    local f=1
    local i

    for ((i=1; i<=$1; ++i)); do f=$((f*i)); done
    echo $f
}

# Calculate the combinations of $1 choose $2
comb()
{
    local c;
    local fn=$(fact $1)
    local fm=$(fact $2)
    local fnm=$(fact $(($1-$2)))

    echo $((fn / fm / fnm))
}

# Sum the combinations of 19 choose m, as m = 4 .. 19.
n=19
sum=0
for ((m=4; m<=n; m++)); do
     sum=$((sum + $(comb $n $m)));
done

echo $sum

#EOF

当然，您必须手动删除重复项。:-)

于 2009-12-31T23:34:38.930 回答
1

我认为这就是你要找的：

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

我将测试功能的实现留给您，因为您没有在原始问题中提供。我的实现基本上将所有 4 个字节或更多字节的序列视为通过测试，因此它会打印所有组合。

我使用了一个递归算法，它以一个空序列和一个字节“池”中的所有 19 个字节开始。然后我通过将池的第一个字节移动到我正在构建的序列中进行递归，然后完全忽略池的第一个字节。

于 2010-01-01T00:09:11.773 回答
0

基本上，您要求的是长度为 (23*8) == 184 位的二进制数。我相信这样的数字比宇宙中的原子还要多！组合数为 2 ** (23 * 8)。

要思考为什么会这样，只需意识到这是一个简单的彩票，其中允许数字重复。您为第一个字节选择一个数字，该数字可以在 0 到 255 之间（256 个选项）。然后你为第二个字节选择一个数字，它可以在 0 到 255 之间，所以你有 (256 * 256) 选项。然后你为第三个字节选择一个数字，它可以在 0 到 255 之间，所以你有 (256 * 256 * 256) 选项（此时为 1600 万，还有 20 个字节......）

您还允许更短的数字这一事实确实为 2 ** 184 可能的字节排列数量增加了一点点，但还不足以显着改变问题的易处理性。

于 2009-12-31T22:50:11.453 回答
0

问题中最重要的部分是字节的顺序不能改变。

让我们从第一个简化的问题开始：

  1. 假设每个数字都是不同的。（显然是假的）
  2. 假设您对选择的数量没有下限（也显然是错误的）

然后你对每个数字都有一个简单的选择：我应该包括这个数字吗？（顺序已经给出。）对于这个简化的问题，你只有 2 19 =524288 种可能性。这需要一段时间才能打印出来，但它足够小，可以计算。

删除任何一个简化都会给您带来更少的可能性。

所以，让我们去掉第一个简化。当您查看一个唯一号码时，您有两种选择：要么将该号码放入您的组合中，要么将其排除在外。当您查看 n 个 00 的序列时，您有n +1 个选择：不将 00 放入组合中，将一个 00 放入组合中，...，将n 00 放入组合中。

因此，此时您有 2 * 4 * 2 5 * 7 * 2 4 = 28672 个选择。

我让你弄清楚这些选择中有多少具有 3 个字节或更少。

于 2009-12-31T23:04:08.060 回答