Наборы подмножеств в & quot; n & quot; объект
Допустим, у меня есть 2 элемента {a,b}, Теперь, учитывая число «n», я хочу иметь все наборы подмножеств «n» элементов таким образом, чтобы при их добавлении все они включали все «n» элементов. Ибо здесь мы можем иметь множество подмножеств ({a} and {b}) а также ({a,b}), В наборе из трех элементов {a,b,c}У меня есть все наборы подмножеств ({a},{b},{c}) а также ({a,b},{c}) а также ({a},{b,c}) а также ({a,c},{b}) а также ({a,b,c}), Как я могу написать программу на C++ в качестве функции взять число «n» и дать мне все наборы этих подмножеств.
Решение
Я не уверен, что понимаю ваш вопрос очень хорошо, но я думаю, что вы смотрите на разделы.
Думайте о проблеме рекурсивно.
Чтобы разделить набор из n элементов, запустите цикл, который повторяется по всем его подмножествам.
Теперь просто добавьте разделы дополнения к подмножеству (которое вы найдете с помощью рекурсии) к подмножеству, которое вы сейчас итерируете.
Другие решения
Вы можете сделать это, используя формулу для нахождения комбинации из n вещей, взятых по r за раз.
nCr = n! / r! (n-r)!
например, чтобы найти все комбинации набора из 3, принимая 2 вещи за один раз (a, b, c) (a, b), …
C = 3! / 2! (3-2)!
C = 6 / 2(1)
C = 3 distinct combinations are possible for set (a,b,c) in a subset of 2:
(a,b), (a,c), (b,c)
finding all of them
nCr(where n and r = 3) = 1 set (a,b,c)
nCr(n=3, r=1) = 3 = 3 sets (a),(b),(c)
include empty set {}
C = 8
чтобы найти все возможные множества, вы можете использовать цикл for для уменьшения r до 0. Из того, что я помню о комбинаторике / перестановках, также считается нулевой набор {}.
вот как это будет выглядеть в функции c ++ (это довольно просто)
unsigned int factorial(unsigned int i)
{
unsigned int sum = 0;
if (i > 1)
{
sum = i;
--i;
for (i; i > 1; --i)
sum *= i;
}// 1! and 0! are 1
else
return 1;return sum;
}
unsigned int allsubsets(unsigned int n)
{
unsigned int C = 0;
for (int r = n; r > 0; --r)
{
C += ( factorial(n) / ( factorial(r) * factorial(n-r) ) );
}
++C; // include the null set
return C;
}
int main()
{
std::cout << "C of 1 is: " << allsubsets(1) << std::endl;
std::cout << "C of 2 is: " << allsubsets(2) << std::endl;
std::cout << "C of 3 is: " << allsubsets(3) << std::endl;
std::cout << "C of 4 is: " << allsubsets(4) << std::endl;
std::cout << "C of 5 is: " << allsubsets(5) << std::endl;
return 0;
}
печатает:
C of 1 is: 2
C of 2 is: 4
C of 3 is: 8
C of 4 is: 16
C of 5 is: 32