Обмен определенными элементами подмножества и добавление подмножеств в коллекцию: Как написать программу, которая проверяет теорию Matroid?

Question

Это на самом деле проблема дискретной математики, но она включает в себя написание программы. Это точный вопрос:

Придумайте программу, которая проверяет, удовлетворяет ли коллекция C «свойству хрупкого обмена (FEP) ниже»

Определение "хрупкой биржевой собственности":

Пусть C - набор из k-элементных подмножеств [n]: = {1, ..., n}.

Для коллекции C мы говорим, что она имеет свойство хрупкого обмена, если для любой пары A, B из C существует a в AB и b в BA, такой что A \ {a} + {b} находится в C.

Другая часть проблемы заключается в следующем:

Создайте коллекцию, которая удовлетворяет FEP, но добавление любого набора в коллекцию лишает его FEP. (попробуйте для k> = 3 и n> = 6, так как в противном случае это невозможно)

Эта часть не является обязательной, но на самом деле ОГРОМНАЯ сумма дополнительных кредитов, и если мы создаем программу, которая проверяет, удовлетворяет ли коллекция этой теории, насколько труднее было бы заставить программу тестировать каждую возможную комбинацию, и вывести коллекцию, что при добавлении любого другого возможного подмножества FEP не работает?

«Хрупкое свойство обмена» на самом деле является теорией Матроидов, поэтому я бы порекомендовал найти ее, если у вас возникли проблемы с пониманием вопроса, поскольку это помогло мне при попытке выяснить его.

---

По сути, скажем, ваша коллекция {1,2,3} {1,2,4} {1,2,5}. Это удовлетворило бы FEP, потому что при обмене третьим элементом всех подмножеств с любым другим подмножеством вы всегда получите новое подмножество, которое уже находится в коллекции. Например: замена третьего элемента {1,2,3} на третий элемент {1,2,4} даст вам {1,2,4} и {1,2,3}.

Мне сказали, что это будет проще всего написать на Python, однако я не очень знаком с Python.

Ранее сегодня я обратился к репетитору по информатике за помощью по этой проблеме, и он помог мне написать следующий код на Python. Может быть несколько ошибок, но я считаю, что это может быть началом того, чего хочет профессор дискретной математики.

# Function which returns subset or r length from n 
from itertools import combinations 

def rSubset(arr, r): 

    # return list of all subsets of length r 
    # to deal with duplicate subsets use  
    # set(list(combinations(arr, r))) 
    return set(combinations(arr, r)) 

def testall(collection, A, B):
    C = set()
    D = set()
    for a in A:
        if a in B:
            continue
        else:
            for b in B:
                if b in A:
                    continue
                else:
                    C,D = exchange(A,B, a,b)
                    if C in collection or D in collection:
                        return True
                    else:
                        return False


def exchange (A,B, a, b):
    if a in B or b in A:
        return
    else:
        index1= A.index(a)
        index2= B.index(b)
        A[index1] = b
        B[index2] = a
        return A, B


# Driver Function 
if __name__ == "__main__": 
    arr = range(1,7) 
    r = 3
    arr2 =  (rSubset(arr, r)) 

    for set1 in arr2:
        for set2 in arr2:
            testall(arr2, set1, set2)