blocks|key|51727|text|使用combinatorial+numbers可能会取得一些成功，它允许您使用一个简单的算法检索第N(+n/10+)k-组合；然后在10个节点中的每一个节点上运行next_combination算法n/10次以进行迭代。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|51728|可以在MSDN上找到示例代码(用C#编写，但对于C%2B%2B程序员来说非常容易阅读)。|51729|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Combinatorial_number_system|1|http://msdn.microsoft.com/en-us/library/aa289166%2528VS.71%2529.aspx^0|29|G|2|L|0|0|3|4|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]]|D|@$9|U|A|V|1|W]]|E|$]]|$1|F|3|G|5|6|7|X|8|@]|D|@$9|Y|A|Z|1|10]]|E|$]]|$1|H|3|-4|5|6|7|11|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]|P|$5|K|L|M|E|$N|Q]]]]

You may have some success with <a href="http://en.wikipedia.org/wiki/Combinatorial_number_system" rel="nofollow">combinatorial numbers</a>, which allow you to retrieve the N'th (n/10th) k-combination with a simple algorithm; then run the <code>next_combination</code> algorithm n/10 times on each of the ten nodes to iterate.

Sample code (in C#, but quite readable for a C++ programmer) can be found on <a href="http://msdn.microsoft.com/en-us/library/aa289166%28VS.71%29.aspx" rel="nofollow">MSDN</a>.

blocks|key|2535169|text|让节点编号n从第n个开始，每十个组合处理一次。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2535170|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Have node number n process every tenth combination, starting from the nth.

blocks|key|2535224|text|我知道这个问题很老了，但这里是如何有效地解决这个问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2535225|所有当前使用Python语言编写的代码都可以很容易地转换为C%2B%2B。|2535226|2535227|您可能希望将特征向量从使用整数改为使用位数组，因为使用的整数将需要500位(在Python中这不是问题)|unordered-list-item|2535228|可以随时更新到C%2B%2B+anyone。|2535229|2535230|2535231|2535232|将它们的组合范围(start+number和length+to+process)、从中选择组合的items集合以及要处理的项数k分发到节点，方法是让每个节点直接从start中找到其起始组合，并通过让每个节点对第一个组合执行工作，然后迭代其其余组合，并执行相关工作来完成相关工作。|ordered-list-item|offset|length|style|CODE|2535233|2535234|2535235|要执行1选择，请按照您的建议查找n--k并将其划分为多个范围-在您的例子中为500-Choose-5是，如您所说的255244687600，因此，对于node=0+To+9，您可以分发：|BOLD|2535236|(start=node*25524468760,+length=25524468760,+items=items,+k=5)|2535237|要执行2，您可以使用组合数字系统直接找到起始组合(无需迭代)，同时找到组合特征向量的整数表示(用于3中的迭代)：|2535238|def+getCombination(index,+items,+k):
++++'''Returns+(combination,+characteristicVector)
++++combination+-+The+single+combination,+of+k+elements+of+items,+that+would+be+at
++++the+provided+index+if+all+possible+combinations+had+each+been+sorted+in
++++descending+order+(as+defined+by+the+order+of+items)+and+then+placed+in+a
++++sorted+list.
++++characteristicVector+-+an+integer+with+chosen+item's+bits+set.
++++'''
++++combination+=+[]
++++characteristicVector+=+0
++++n+=+len(items)
++++nCk+=+1
++++for+nMinusI,+iPlus1+in+zip(range(n,+n+-+k,+-1),+range(1,+k+%2B+1)):
++++++++nCk+*=+nMinusI
++++++++nCk+//=+iPlus1
++++curIndex+=+nCk
++++for+k+in+range(k,+0,+-1):
++++++++nCk+*=+k
++++++++nCk+//=+n
++++++++while+curIndex+-+nCk+>+index:
++++++++++++curIndex+-=+nCk
++++++++++++nCk+*=+(n+-+k)
++++++++++++nCk+-=+nCk+%25+k
++++++++++++n+-=+1
++++++++++++nCk+//=+n
++++++++n+-=+1
++++++++combination+.append(items[n])
++++++++characteristicVector+%2B=+1+<<+n
++++return+combination,+characteristicVector+|code-block|syntax|javascript|2535239|特征向量的整数表示在组成组合的项目的位置设置了k个比特。|2535240|要执行3，您可以使用Gosper的hack来迭代到相同数字系统中组合的下一个特征向量(相对于items出现在反向排序组合的排序列表中的下一个组合)，同时创建组合：|2535241|def+nextCombination(items,+characteristicVector):
++++'''Returns+the+next+(combination,+characteristicVector).
++++combination+-+The+next+combination+of+items+that+would+appear+after+the
++++combination+defined+by+the+provided+characteristic+vector+if+all+possible
++++combinations+had+each+been+sorted+in+descending+order+(as+defined+by+the+order
++++of+items)+and+then+placed+in+a+sorted+list.
++++characteristicVector+-+an+integer+with+chosen+item's+bits+set.
++++'''
++++u+=+characteristicVector+&+-characteristicVector
++++v+=+u+%2B+characteristicVector
++++if+v+<=+0:
++++++++raise+OverflowError("Ran+out+of+integers")+#+<-+ready+for+C%2B%2B
++++characteristicVector+=++v+%2B+(((v+%5E+characteristicVector)+//+u)+>>+2)
++++combination+=+[]
++++copiedVector+=+characteristicVector
++++index+=+len(items)+-+1
++++while+copiedVector+>+0:
++++++++present,+copiedVector+=+divmod(copiedVector,+1+<<+index)
++++++++if+present:
++++++++++++combination.append(items[index])
++++++++index+-=+1
++++return+combination,+characteristicVector|2535242|重复此length-1次数(因为您已经直接找到了第一个)。|2535243|2535244|为例：|2535245|处理7-letters+3字母的五个节点：|2535246|>>>+items+=+('A','B','C','D','E','F','G')
>>>+k+=+3
>>>+nodes+=+5
>>>+n+=++len(items)
>>>+for+nmip1,+i+in+zip(range(n+-+1,+n+-+k,+-1),+range(2,+k+%2B+1)):
...+++++n+=+n+*+nmip1+//+i
...
>>>+for+node+in+range(nodes):
...+++++length+=+n+//+nodes
...+++++start+=+node+*+length
...+++++print("Node+{0}+initialised".format(node))
...+++++combination,+cv+=+getCombination(start,+items,+k)
...+++++doWork(combination)
...+++++for+i+in+range(length-1):
...+++++++++++++combination,+cv+=+nextCombination(items,+cv)
...+++++++++++++doWork(combination)
...
Node+0+initialised
Doing+work+with:+C+B+A
Doing+work+with:+D+B+A
Doing+work+with:+D+C+A
Doing+work+with:+D+C+B
Doing+work+with:+E+B+A
Doing+work+with:+E+C+A
Doing+work+with:+E+C+B
Node+1+initialised
Doing+work+with:+E+D+A
Doing+work+with:+E+D+B
Doing+work+with:+E+D+C
Doing+work+with:+F+B+A
Doing+work+with:+F+C+A
Doing+work+with:+F+C+B
Doing+work+with:+F+D+A
Node+2+initialised
Doing+work+with:+F+D+B
Doing+work+with:+F+D+C
Doing+work+with:+F+E+A
Doing+work+with:+F+E+B
Doing+work+with:+F+E+C
Doing+work+with:+F+E+D
Doing+work+with:+G+B+A
Node+3+initialised
Doing+work+with:+G+C+A
Doing+work+with:+G+C+B
Doing+work+with:+G+D+A
Doing+work+with:+G+D+B
Doing+work+with:+G+D+C
Doing+work+with:+G+E+A
Doing+work+with:+G+E+B
Node+4+initialised
Doing+work+with:+G+E+C
Doing+work+with:+G+E+D
Doing+work+with:+G+F+A
Doing+work+with:+G+F+B
Doing+work+with:+G+F+C
Doing+work+with:+G+F+D
Doing+work+with:+G+F+E
>>>|2535247|entityMap^0|0|0|0|0|0|0|0|0|9|5|M|6|1C|5|1R|1|29|5|0|0|0|3|F|0|0|1Q|0|3|1|1D|1|0|0|0|3|1|1A|5|0|0|3|8|0|0|0|3|0|0|0^^$0|@$1|2|3|4|5|6|7|1O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1P|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|1R|8|@]|9|@]|A|$]]|$1|H|3|I|5|G|7|1S|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|1T|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|1V|8|@]|9|@]|A|$]]|$1|M|3|N|5|O|7|1W|8|@$P|1X|Q|1Y|R|S]|$P|1Z|Q|20|R|S]|$P|21|Q|22|R|S]|$P|23|Q|24|R|S]|$P|25|Q|26|R|S]]|9|@]|A|$]]|$1|T|3|-4|5|6|7|27|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|28|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|29|8|@$P|2A|Q|2B|R|X]]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|2C|8|@$P|2D|Q|2E|R|S]]|9|@]|A|$]]|$1|10|3|11|5|6|7|2F|8|@$P|2G|Q|2H|R|X]|$P|2I|Q|2J|R|X]]|9|@]|A|$]]|$1|12|3|13|5|14|7|2K|8|@]|9|@]|A|$15|16]]|$1|17|3|18|5|6|7|2L|8|@]|9|@]|A|$]]|$1|19|3|1A|5|6|7|2M|8|@$P|2N|Q|2O|R|X]|$P|2P|Q|2Q|R|S]]|9|@]|A|$]]|$1|1B|3|1C|5|14|7|2R|8|@]|9|@]|A|$15|16]]|$1|1D|3|1E|5|6|7|2S|8|@$P|2T|Q|2U|R|S]]|9|@]|A|$]]|$1|1F|3|-4|5|6|7|2V|8|@]|9|@]|A|$]]|$1|1G|3|1H|5|6|7|2W|8|@$P|2X|Q|2Y|R|X]]|9|@]|A|$]]|$1|1I|3|1J|5|6|7|2Z|8|@]|9|@]|A|$]]|$1|1K|3|1L|5|14|7|30|8|@]|9|@]|A|$15|16]]|$1|1M|3|-4|5|6|7|31|8|@]|9|@]|A|$]]]|1N|$]]

I know this question is old, but here is how it may be done efficiently.

All code currently in Python which I'm sure will be easy enough to translate to C++. - You will probably want to move from using an integer for the characteristic vector to using a bit array, since the integers used will need 500 bits (not a problem in Python) - Feel free to update to C++ anyone.

<hr>

<ol>
<li>Distribute to the nodes their range of combinations (<code>start</code> number and <code>length</code> to process), the set of <code>items</code> from which combinations are to be chosen, and the number, <code>k</code>, of items to choose.</li>
<li>Initialise each node by having it find its starting combination directly from <code>start</code> and <code>items</code>.</li>
<li>Run each node by having it do the work for the first combination then iterate through the rest of its combinations, and do the associated work.</li>
</ol>

<hr>

To perform 1 do as you suggest find n-choose-k and divide it into ranges - in your case 500-Choose-5 is, as you said, 255244687600 so, for node=0 to 9 you distribute: <code>(start=node*25524468760, length=25524468760, items=items, k=5)</code>

To perform 2 you can find the starting combination directly (without iteration) using the combinatorial number system and find the integer representation of the combination's characteristic vector (to be used for the iteration in 3) at the same time:

<pre><code>def getCombination(index, items, k):
 '''Returns (combination, characteristicVector)
 combination - The single combination, of k elements of items, that would be at
 the provided index if all possible combinations had each been sorted in
 descending order (as defined by the order of items) and then placed in a
 sorted list.
 characteristicVector - an integer with chosen item's bits set.
 '''
 combination = []
 characteristicVector = 0
 n = len(items)
 nCk = 1
 for nMinusI, iPlus1 in zip(range(n, n - k, -1), range(1, k + 1)):
 nCk *= nMinusI
 nCk //= iPlus1
 curIndex = nCk
 for k in range(k, 0, -1):
 nCk *= k
 nCk //= n
 while curIndex - nCk &gt; index:
 curIndex -= nCk
 nCk *= (n - k)
 nCk -= nCk % k
 n -= 1
 nCk //= n
 n -= 1
 combination .append(items[n])
 characteristicVector += 1 &lt;&lt; n
 return combination, characteristicVector 
</code></pre>

The integer representation of the characteristic vector has k bits set in the positions of the items that make up the combination.

To perform 3 you can use Gosper's hack to iterate to the next characteristic vector for the combination in the same number system (the next combination that would appear in a sorted list of reverse sorted combinations relative to <code>items</code>) and, at the same time, create the combination:

<pre><code>def nextCombination(items, characteristicVector):
 '''Returns the next (combination, characteristicVector).
 combination - The next combination of items that would appear after the
 combination defined by the provided characteristic vector if all possible
 combinations had each been sorted in descending order (as defined by the order
 of items) and then placed in a sorted list.
 characteristicVector - an integer with chosen item's bits set.
 '''
 u = characteristicVector &amp; -characteristicVector
 v = u + characteristicVector
 if v &lt;= 0:
 raise OverflowError("Ran out of integers") # &lt;- ready for C++
 characteristicVector = v + (((v ^ characteristicVector) // u) &gt;&gt; 2)
 combination = []
 copiedVector = characteristicVector
 index = len(items) - 1
 while copiedVector &gt; 0:
 present, copiedVector = divmod(copiedVector, 1 &lt;&lt; index)
 if present:
 combination.append(items[index])
 index -= 1
 return combination, characteristicVector
</code></pre>

Repeat this <code>length-1</code> times (since you already found the first one directly).

<hr>

For example:

Five nodes processing 7-choose-3 letters:

<pre><code>&gt;&gt;&gt; items = ('A','B','C','D','E','F','G')
&gt;&gt;&gt; k = 3
&gt;&gt;&gt; nodes = 5
&gt;&gt;&gt; n = len(items)
&gt;&gt;&gt; for nmip1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)):
... n = n * nmip1 // i
...
&gt;&gt;&gt; for node in range(nodes):
... length = n // nodes
... start = node * length
... print("Node {0} initialised".format(node))
... combination, cv = getCombination(start, items, k)
... doWork(combination)
... for i in range(length-1):
... combination, cv = nextCombination(items, cv)
... doWork(combination)
...
Node 0 initialised
Doing work with: C B A
Doing work with: D B A
Doing work with: D C A
Doing work with: D C B
Doing work with: E B A
Doing work with: E C A
Doing work with: E C B
Node 1 initialised
Doing work with: E D A
Doing work with: E D B
Doing work with: E D C
Doing work with: F B A
Doing work with: F C A
Doing work with: F C B
Doing work with: F D A
Node 2 initialised
Doing work with: F D B
Doing work with: F D C
Doing work with: F E A
Doing work with: F E B
Doing work with: F E C
Doing work with: F E D
Doing work with: G B A
Node 3 initialised
Doing work with: G C A
Doing work with: G C B
Doing work with: G D A
Doing work with: G D B
Doing work with: G D C
Doing work with: G E A
Doing work with: G E B
Node 4 initialised
Doing work with: G E C
Doing work with: G E D
Doing work with: G F A
Doing work with: G F B
Doing work with: G F C
Doing work with: G F D
Doing work with: G F E
&gt;&gt;&gt;
</code></pre>

I have a problem where I must analyse 500C5 combinations (255244687600) of something. Distributing it over a 10-node cluster where each cluster processes roughly 10^6 combinations per second means the job will be complete in about seven hours.

The problem I have is distributing the 255244687600 combinations over the 10 nodes. I'd like to present each node with 25524468760, however the algorithms I'm using can only produce the combinations sequentially, I'd like to be able to pass the set of elements and a range of combination indicies, for example, [0-10^7), [10^7,2.0 10^7), etc. and have the nodes themselves figure out the combinations.

The algorithms I'm using at the moment are from the following:

<ul>
<li><a href="http://howardhinnant.github.io/combinations.html" rel="nofollow noreferrer">http://howardhinnant.github.io/combinations.html</a></li>
<li>Stack Overflow question <a href="https://stackoverflow.com/questions/4590075/a-logical-question/4590954#4590954">Efficiently computing vector combinations</a></li>
</ul>

I've considered using a master node, that enumerates each of the combinations and sends work to each of the nodes. However, the overhead incurred in iterating the combinations from a single node and communicating back and forth work is enormous, and it will subsequently lead to the master node becoming the bottleneck.

Is there any good combination iterating algorithms geared up for efficient/optimal distributed enumeration?

Enumerating combinations in a distributed manner

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有一个问题，我必须分析某些东西的500C5组合(255244687600)。将它分布在一个10个节点的集群上，每个集群每秒处理大约10^6个组合，这意味着该作业将在大约7小时内完成。我遇到的问题是将255244687600个组合分布在10个节点上。我想用25524468760表示每个节点，但是我使用的算法只能按顺序产...

问以分布式方式枚举组合
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问以分布式方式枚举组合EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问以分布式方式枚举组合
EN