1

現在、IPマルチキャストを調査しており、N個のホストのすべての可能な組み合わせに対応するために必要な一意のマルチキャストグループの数を決定しています。

たとえば、3つのエンドホスト（A、B、C）がある場合、これらのホストのすべての可能な組み合わせ（AB、AC、BC、ABC）をアドレス指定できるようにするには、合計4つのマルチキャストグループを作成する必要があります。 1つまたは0つのホストがアドレス指定されているインスタンス。

私の知る限り、1つまたは0のホストがアドレス指定されているインスタンスを除く一意のグループの数は、[2 ^ N-（N + 1）]として表すことができます。ここで、N=ホストの数です。

ただし、少なくとも特定の割合のシステムのみがアドレス指定されている場合に、いくつのグループが存在するかを調べることに興味があります。

たとえば、5つのシステムがある場合、合計26のマルチキャストグループがあります。ただし、3つ以下のシステムがアドレス指定されているグループを除外した場合（グループのみが4つであるか、すべてのシステムがアドレス指定されている）、6つのグループしかありません。以下に示すように、これは手作業で判断できます。

代わりにこれを計算するために使用できる式はありますか？したがって、N個のホストがあり、Y個以上のホストを含​​むマルチキャストグループのみを作成する場合は、Z個のマルチキャストグループがあることを意味します。上記の例では、Y = 4、Zは6と決定されます。

支援やフィードバックは常にありがたいです

1 with 0 bits set
00 - 00000

5 with 1 bit set
01 - 00001
02 - 00010
04 - 00100
08 - 01000
16 - 10000

10 with 2 bits set
03 - 00011
05 - 00101
06 - 00110
09 - 01001
10 - 01010
12 - 01100
18 - 10010
20 - 10100
17 - 10001
24 - 11000

10 with 3 bits set
07 - 00111
11 - 01011
13 - 01101
14 - 01110
19 - 10011
21 - 10101
22 - 10110
25 - 11001
26 - 11010
28 - 11100

5 with 4 bits set
15 - 01111
23 - 10111
27 - 11011
29 - 11101
30 - 11110

1 with 5 bits set
31 - 11111
4

2 に答える 2

3 
Sum[i=0 to N] N{C}i = Sum of all combinations of i hosts out of N hosts = 2^N
--- [1] 
Sum[i=0 to Y] N{C}i = Sum of all combinations of multicast groups with Y or fewer hosts, including single hosts. 
--- [2]

あなたは（[1]-[2]）を探しています。

于 2012-06-05T17:48:50.560 に答える
2

これを組み合わせの問題のように扱うと役立つはずです。http://en.wikipedia.org/wiki/Combinationを参照してください

Nビットのうち、YからNビットが設定されている組み合わせの合計を知りたい。

この擬似コードのようなもの：

for k from Y..N
  total += (N choose k)

どこN choose kで計算できますかN! / (k! * (N-k)!)

あなたの例では、次のようになります。

5 choose 4 = 5
5 choose 5 = 1
--------------
     total = 6
于 2012-06-05T17:59:17.430 に答える