Перечисление комбинаций распределенным образом

Ответ 1

У вас может быть некоторый успех с комбинаторными номерами, которые позволят вам получить k-комбинацию N'th (n/10th) с простой алгоритм; затем запустите алгоритм next_combination n/10 раз на каждом из десяти узлов для итерации.

Пример кода (в С#, но вполне читаемый для программиста на С++) можно найти на MSDN.

Ответ 2

Иметь node число n обрабатывать каждую десятую комбинацию, начиная с n-го.

Ответ 3

Я знаю, что этот вопрос старый, но вот как это можно сделать эффективно.

Весь код, находящийся в настоящее время на Python, который, я уверен, будет достаточно простым для перевода на С++.
- Вам, вероятно, захочется перейти от использования целого для вектор-характеристики к использованию битового массива, поскольку целые числа для использования потребуется 500 бит (не проблема в Python)
- Не стесняйтесь обновлять до любого С++.

• Распределите узлы их диапазон комбинаций (start number и length для обработки), набор items, из которого должны быть выбраны комбинации, и число, k, элементов для выбора.
• Инициализируйте каждый node, если он найдет свою стартовую комбинацию непосредственно из start и items.
• Запустите каждый node за счет того, что он выполняет работу для первой комбинации, затем перебирает остальные ее комбинации и выполняет соответствующую работу.

Чтобы выполнить 1 сделать так, как вы предлагаете найти n-select-k и разделить его на диапазоны - в вашем случае 500-Select-5, как вы сказали, 255244687600, поэтому для node= 0 до 9 вы распространяете:
(start=node*25524468760, length=25524468760, items=items, k=5)

Чтобы выполнить 2, вы можете сразу же найти стартовую комбинацию (без итерации) с использованием комбинаторной числовой системы и найти целочисленное представление комбинационного характеристического вектора (который будет использоваться для итерации в 3):

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 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 > index:
            curIndex -= nCk
            nCk *= (n - k)
            nCk -= nCk % k
            n -= 1
            nCk //= n
        n -= 1
        combination .append(items[n])
        characteristicVector += 1 << n
    return combination, characteristicVector 

Целочисленное представление характеристического вектора имеет k бит, заданных в позициях элементов, составляющих комбинацию.

Для выполнения 3 вы можете использовать Gosper hack для итерации к следующему характеристическому вектору для комбинации в той же системе счисления (следующая комбинация, которая появится в отсортированном списке комбинаций с обратной сортировкой относительно items) и в то же время создать комбинацию:

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 bits set.
    '''
    u = characteristicVector & -characteristicVector
    v = u + characteristicVector
    if v <= 0:
        raise OverflowError("Ran out of integers") # <- ready for C++
    characteristicVector =  v + (((v ^ 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

Повторите этот length-1 раз (поскольку вы уже нашли первый файл напрямую).

Например:

Пять узлов, обрабатывающих 7-выбирают-3 буквы:

>>> 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 + 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
>>>