Блог

У меня есть n-кортеж, x = (x[0], .., x[n-1]) где каждый член кортежа происходит из отдельного упорядоченного множества S[i] , такого, что x[i] in S[i] . Все наборы S[i] имеют разную мощность N[i] . Я хочу знать, как сгенерировать следующий кортеж в лексическом порядке с учетом наборов S[i] .

Пример:

 S[0] = {0,1,2}
S[1] = {1,2,3,4}
S[2] = {8,9,7}

x = {2,2,7}
xnext = {2,3,8}
xnextnext = {2,3,9}
 

и т. д

Это не обязательно должно быть очень эффективным, просто замкнутая форма с точки зрения текущих элементов кортежа и наборов. Если это проще, было бы эквивалентно думать о n-кортеже как об индексах в наборах.

Для данного кортежа вы можете сопоставить элементы кортежа с их соответствующими индексами в каждом наборе S , а затем попытаться «увеличить» число со смешанным основанием, представленное этим кортежем индексов. Затем возьмите увеличенное «число» и сопоставьте его обратно с кортежем элементов. Вот доказательство концепции в Python:

 def next_tuple(x, S):
    assert len(x) == len(S)
    assert all(element in set_ for element, set_ in zip(x, S))

    # compute the bases for our mixed-radix system
    lengths = [len(set_) for set_ in S]
    # convert tuple `x` to a mixed-radix number
    indices = [set_.index(element) for element, set_ in zip(x, S)]

    # try to increment, starting from the right
    for k in reversed(range(len(indices))):
        indices[k]  = 1

        if indices[k] == lengths[k]: 
            # case 1: we have a carry, rollover this index and continue
            indices[k] = 0
        else:
            # case 2: no carry, map indices back to actual elements and return
            return [set_[index] for index, set_ in zip(indices, S)]

    # we have gone through each position and still have a carry.
    # this means the "increment" operation overflowed, and there
    # is no "next" tuple.
    return None


S = [[0, 1, 2], [1, 2, 3, 4], [8, 9, 7]]

print("next tuple after {} is {}".format([2, 2, 7], next_tuple([2, 2, 7], S)))
print("all tuples in order:")

x = [0, 1, 8]

while x is not None:
    print(x)
    x = next_tuple(x, S)
 

В качестве последнего замечания, если вам нужно перечислить все декартово произведение по порядку, проще использовать прямой алгоритм, а не повторное использование next_tuple , которое каждый раз требует пересчета индексов.

Я заставил его работать, используя этот псевдокод:

 # x = [2,2,7]
sets = [[0,1,2], [1,2,3,4], [8,9,7]]
def next_tuple(x):
    for i, el in enumerate(x):
        if(i < len(sets[i]) - 1):
            x[i] = sets[i, sets[i].index(x[i]) 1] // requires lists to have unique elements
            return x
        else :
            x[i] = sets[i,0]
 

По сути, вы сканируете символ из кортежа и, если его можно увеличить, увеличиваете его. Если нет, установите для него значение 0 и перейдите к следующему символу.