Проблема: Начните с набора S размера 2n + 1 и подмножества A из S размера n. У вас есть функции addElement(A,x) и removeElement(A,x), которые могут добавлять или удалять элементы A. Напишите функцию, которая перебирает все подмножества S размера n или n + 1, используя только эти две операции над A.
Я выяснил, что есть (2n + 1 выберите n) + (2n + 1 выберите n + 1) = 2 * (2n + 1 выберите n) подмножества, которые мне нужно найти. Итак, вот структура моей функции:
for (int k=0; k<2*binomial(2n+1,n); ++k) {
if (k mod 2) {
// somehow choose x from S-A
A = addElement(A,x);
printSet(A,n+1);
} else
// somehow choose x from A
A = removeElement(A,x);
printSet(A,n);
}
}
Функция binomial(2n+1,n) просто дает биномиальный коэффициент, а функция printSet печатает элементы A, чтобы я мог видеть, ударил ли я все множества.
Хотя я не знаю, как выбрать элемент для добавления или удаления. Я пробовал много разных вещей, но в целом ничего не получалось.
Для n = 1, я нашел решение, которое работает:
for (int k=0; k<6; ++k) {
if (k mod 2) {
x = S[A[0] mod 3];
A = addElement(A,x);
printSet(A,2);
} else
x = A[0];
A = removeElement(A,x);
printSet(A,1);
}
}
и вывод для S = [1,2,3] и A=[1]:
[1,2]
[2]
[2,3]
[3]
[3,1]
[1]
Но даже заставить это работать для n = 2 я не могу сделать. Может кто-нибудь помочь мне с этим?