Перечисление перестановок по порядку. Генерация i-ой перестановки без вычисления предыдущих.

SequencingPermutation.py

import math


class SequencePermutation(object):
    def __init__(self, plenty_object, count_item):
        self.plenty_object = list(plenty_object)
        self.count_item = count_item
        self.power_plenty = len(plenty_object)

    @staticmethod
    def calc_count_permutation(n, k):
        """
        Подсчёт колличество размещений из n по к
        :param n: 
        :param k:  
        :return: int колличестов размещений
        """
        return int(math.factorial(n) / math.factorial(n - k))

    def __getitem__(self, index):
        """
        Вычисление index перестановки
        :param index: порядковый номер перестановки
        :return: лист содеражащий перестановку
        """
        current_mod = index
        plenty = self.plenty_object.copy()
        for i in range(self.count_item - 1):
            perm_count = self.calc_count_permutation(self.power_plenty - i - 1, self.count_item - i - 1)
            current_index = current_mod // perm_count
            yield plenty[current_index]
            plenty.pop(current_index)
            current_mod = current_mod % perm_count
        yield plenty[current_mod]

def simple_calc_permutation(plenty_object, count_item):
    """
    Генерация всех перестоновок размера count_item из множество объектов plenty_object
    :param plenty_object: множество объектов
    :param count_item: колчество элементов в перестановке
    :return: генератор множества перестановок
    """
    assert count_item > 0
    # мощьность множествы объектов
    power = len(plenty_object)
    if count_item == 1:
        for o in plenty_object:
            yield [o]
    else:
        for i in range(power):
            # отщипление первого элемента перестановки
            excluded_plenty = list(plenty_object).copy()
            excluded_plenty.pop(i)
            for perm in simple_calc_permutation(excluded_plenty, count_item - 1):
                begin_perm = [plenty_object[i]]
                begin_perm.extend(perm)
                yield begin_perm


def test_simple_calc_permutation():
    expected = [[0, 1], [0, 2],
                [1, 0], [1, 2],
                [2, 0], [2, 1]]
    # print(list(simple_calc_permutation(range(3), 2)))
    assert expected == list(simple_calc_permutation(range(3), 2))


def test_sequence_permutation(n, k):
    plenty_object = range(n)
    # количество элементов в одной перестановки
    count_item = k
    sq_per = SequencePermutation(plenty_object, count_item)
    all_permutation = simple_calc_permutation(plenty_object, count_item)
    index = 0
    for permutation in all_permutation:
        if sq_per[index] != permutation:
            print(index)
            print(permutation)
            print(sq_per[index])
            print("---------------")
        assert sq_per[index] == permutation
        index += 1


def test_sequence_permutation_on_different_params():
    for i in range(1, 9):
        for j in range(1, i):
            test_sequence_permutation(i, j)


if __name__ == "__main__":
    test_sequence_permutation_on_different_params()