Индекс в упорядоченный набор мощности

Я хотел бы иметь возможность индексировать элементы набора мощности без расширения полного набора в память (a la itertools)

Кроме того, я хочу, чтобы индекс был задан мощностью. Таким образом, индекс 0 должен быть пустым, индекс 2 ** n - 1 должен быть всеми элементами

Большая часть литературы, которую я нашел до сих пор, включает индуктивную индукцию. Это не позволяет вам просто погрузиться в любой индекс. Мотивация для этой индексации - разрезать проблему для распределенного выполнения, и полезно, если удаленная машина может просто погрузиться в любом месте без совместного использования ссылки итератора через кластер.

EDIT: Blckknght предложил решение, которое я преследовал, которое показано ниже

from scipy.misc import comb

def kcombination_to_index(combination):
    index = 0
    combination = sorted(combination)
    for k, ck in enumerate(combination):
        index += comb(ck, k+1, exact=True)
    return index

def index_to_kcombination(index, k):
    result = []
    for k in reversed(range(1, k+1)):
        n = 0
        while comb(n, k, exact=True) <= index:
            n +=1
        result.append(n-1)
        index -= comb(n-1, k, exact=True)

    return result

class PowerSet:
    def __init__(self, elements):
        self.elements = elements

    def __len__(self):
        return 2 ** len(self.elements)

    def __iter__(self):
        for i in range(len(self)):
            yield self[i]

    def __getitem__(self, k):
        if not isinstance(k, int):
            raise TypeError
        #k=0 is empty set,
        #k= 1 - 1+n returns subsets of size 1
        for subset_size in range(len(self.elements) + 1):
            number_subsets = comb(len(self.elements), subset_size, exact=True)

            if k >= number_subsets:
                k -= number_subsets
            else:
                break

        #we now want the kth element of a possible permutation of subset_size elements
        indeces = index_to_kcombination(k, subset_size)

        return map(lambda i: self.elements[i], indeces)

if __name__ == "__main__":
    print "index of combination [8, 6, 3, 1, 0] is", kcombination_to_index([8, 6, 3, 1, 0])
    print "5 combination at position 72 is", index_to_kcombination(72,5)

    ps = PowerSet(["a", "b", "c", "d"])

    for subset_idx in range(len(ps)):
        print ps[subset_idx]

Ответы

Ответ 1

Я думаю, вы можете сделать это с помощью двухэтапного процесса. Первым шагом является то, что Михай Марусеак описал в своем (теперь удаленном) ответе, чтобы найти размер набора, итерации по возможным размерам, пока не найдете подходящий. Здесь код для этого:

def find_size(n, i):
    """Return a tuple, (k, i), where s is the size of the i-1'th set in the
       cardinally-ordered powerset of {0..n-1}, and i is the remaining index
       within the combinations of that size."""
    if not 0 <= i < 2**n:
        raise ValueError('index is too large or small')
    for k in range(n+1):
        c = comb(n, k)
        if c > i:
            return k, i
        else:
            i -= c

Как только вы определили размер, вы можете использовать комбинаторную систему чисел, чтобы найти правильную k-комбинацию из лексикографического заказа:

def pick_set(n, i):
    """Return the i-1'th set in the cardinally-ordered powerset of {0..n-1}"""
    s, i = find_size(n, i)
    result = []
    for k in range(s, 0, -1):
        prev_c = 0
        for v in range(k, n+1):
            c = comb(v, k)
            if i < c:
                result.append(v-1)
                i -= prev_c
                break
            prev_c = c
    return tuple(result)

Обе эти функции требуют функции для вычисления числа k-комбинаций для набора размеров n, n C k (который я назвал comb). В этом другом вопросе есть несколько предлагаемых решений для поиска этого значения, включая scipy.misc.comb, gmpy.comb и несколько реализаций pure-python. Или, поскольку он неоднократно вызывался с последовательно возрастающими значениями (например, comb(n, 0), comb(n, 1) и т.д. Или comb(k, k), comb(k+1, k) и т.д.), Вы могли вместо этого использовать встроенный расчет, который использует ранее рассчитанное значение, чтобы дать более высокая производительность.

Пример использования (с использованием функции comb, минимально адаптированной из J.F. Sebastian answer в связанном выше вопросе):

>>> for i in range(2**4):
        print(i, pick_set(4, i))

0 ()
1 (0,)
2 (1,)
3 (2,)
4 (3,)
5 (1, 0)
6 (2, 0)
7 (2, 1)
8 (3, 0)
9 (3, 1)
10 (3, 2)
11 (2, 1, 0)
12 (3, 1, 0)
13 (3, 2, 0)
14 (3, 2, 1)
15 (3, 2, 1, 0)

Обратите внимание, что если вы планируете итерацию по комбинациям (как это было в примере), вы можете сделать это более эффективно, чем при запуске полного алгоритма, так как есть более эффективные алгоритмы для поиска следующей комбинации заданного размера (хотя вам понадобится немного дополнительной логики, чтобы подпрыгнуть до следующего большего размера комбинаций, когда вы исчерпали начальный размер).

Изменить: Вот некоторые из описанных выше оптимизаций:

Прежде всего, генераторы, которые эффективно вычисляют значения комбинации для диапазонов значений n или k:

def comb_n_range(start_n, stop_n, k):
    c = comb(start_n, k)
    yield start_n, c
    for n in range(start_n+1, stop_n):
        c = c * n // (n - k)
        yield n, c

def comb_k_range(n, start_k, end_k):
    c = comb(n, start_k)
    yield start_k, c
    for k in range(start_k+1, end_k):
        c = c * (n - k + 1) // k
        yield k, c

Биты for ... in range(...): c = comb(...); ... в приведенном выше коде могут быть скорректированы для их использования, что должно быть немного быстрее.

Далее, функция, которая возвращает следующую комбинацию в лексикографическом порядке:

def next_combination(n, c):
    if c[-1] == n-len(c)+1:
        raise ValueError("no more combinations")
    for i in range(len(c)-1, -1, -1):
        if i == 0 or c[i] < c[i-1] - 1:
            return c[:i] + (c[i] + 1,) + tuple(range(len(c)-2-i,-1,-1))

И генератор, который использует next_combination для получения диапазона значений из набора параметров, определенного объектом slice:

def powerset_slice(n, s):
    start, stop, step = s.indices(2**n)
    if step < 1:
        raise ValueError("invalid step size (must be positive)")

    if start == 0:
        c = ()
    else:
        c = pick_set(n, start)

    for _ in range(start, stop, step):
        yield c
        for _ in range(step):
            try:
                c = next_combination(n, c)
            except ValueError:
                if len(c) == n:
                    return
                c = tuple(range(len(c), -1, -1))

Вы можете интегрировать это в класс, который используете, делая __getitem__ возвращать генератор, если ему передан объект slice, а не int. Это позволит вам быстрее сделать __iter__, просто превратив его тело в: return self[:].