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

これがあなたが探しているものだと思います：

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

元の質問でそれを提供しなかったので、 Test 関数の実装をあなたに任せます。私の実装では、基本的に 4 バイト以上のすべてのシーケンスがテストに合格したものとして扱われるため、すべての組み合わせが出力されます。

空のシーケンスで始まる再帰アルゴリズムと、バイトの「プール」内の 19 バイトすべてを使用しました。次に、プールの最初のバイトを構築中のシーケンスに移動し、プールの最初のバイトを完全に無視して、両方を再帰します。

于 2010-01-01T00:09:11.773 に答える
1

私は最終的に質問を理解したと思います：

あなたは19個のアイテムを持っています.

  • 一度に4つ
  • 一度に5つ
  • ...
  • 一度に19。

一度にm個取られるn 個のアイテムの組み合わせの数は" n choose m "として知られており、次のように計算されます。

             ん！
    ——————
    ( m !) ( n - m )!

したがって、4 から 19 までのmのすべての値に対して(19 choose m )を追加する必要があります。

次のことに注意することで、計算を簡略化できます。

     nを選択m   =   nを選択 ( n - m )

したがって、 m = 4 からm = 9までの組み合わせを計算し、それを 2 倍にしてm = 10 からm = 15 を計算し、 m = 15 から 19までの組み合わせを追加します。

計算を行うための bash シェル スクリプトを次に示します。これは、約 4 分の 1 秒の計算の後に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 に答える
0

基本的に、長さ (23*8) == 184 ビットの 2 進数を求めています。宇宙には原子の数よりも多くの数があると私は信じています！組み合わせの数は 2 ** (23 * 8) です。

これがなぜなのかを考えるには、数字が繰り返される単純な宝くじであることを理解してください。最初のバイトに 1 つの数値を選択します。これは 0 ～ 255 (256 オプション) です。次に、2 番目のバイトの数値を選択します。これは 0 から 255 の間であり、(256 * 256) のオプションがあります。次に、3 番目のバイトの数値を選択します。これは 0 から 255 の間であり、(256 * 256 * 256) のオプションがあります (この時点で 1600 万で、残り 20 バイトです...)

より短い数値も許可するという事実は、可能なバイト配列の数を 2 ** 184 にもう少し追加しますが、問題の扱いやすさを大幅に変えるほどではありません。

于 2009-12-31T22:50:11.453 に答える
0

問題の最も重要な部分は、バイトの順序を変更できないということです。

最初の単純化された問題から始めましょう。

  1. それぞれの数が異なると仮定します。(明らかに嘘)
  2. 選択肢の数に下限はないと仮定します (これも明らかに誤りです)。

次に、各番号について簡単な選択があります。この番号を含めるかどうかを選択します。(順序は既に与えられています。) この単純化された問題では、2 19 =524288 の可能性しかありません。印刷には時間がかかりますが、計算するには十分小さいです。

いずれかの単純化を削除すると、可能性が少なくなります。

それでは、最初の単純化を削除しましょう。一意の番号を見ている場合、その番号を組み合わせに入れるか、除外するかの 2 つの選択肢があります。n 個の00のシーケンスを見ている場合、n +1 個の選択肢があります。組み合わせに 00 を入れない、組み合わせに 00 を 1 個入れる、...、組み合わせにn 個の 00 を入れます。

したがって、この時点で 2 * 4 * 2 5 * 7 * 2 4 = 28672 の選択肢があります。

これらの選択肢のうち、3 バイト以下の選択肢がいくつあるかは、あなたに任せます。

于 2009-12-31T23:04:08.060 に答える