Ответы пользователя по тегу Комбинаторика
  • Как найти все возможные не повторяющиеся пересечения множеств?

    Как я понимаю, общих элементов нет.
    На примере 3-х множеств с мощностями a, b и c.
    m=0: 1 комбинация
    m=1: a + b + c комбинаций
    m=2: a*b + b*c + a*c комбинаций
    m=3: a*b*c комбинаций

    Итого
    1 + a + b + c + ab + bc + ca + abc
    1 + a + b + ab + c*(1 + a + b + ab)
    (1 + a + b + ab)(1 + c)
    ...
    (1 + a)(1 + b)(1 + c)

    На ваших данных получаем 4*3*3 = 36

    Ответ подсказывает и принцип, как его посчитать. Из одного множества можно выбрать 1 + a способами: либо не берём (пустое множество), либо берём a способами.
    Если добавить новое множество в рассмотрение, то либо мы из него не берём элемент, либо тоже берём, b способами, итого: (1+a)(1+b). Т.е. каждое множество Aᵢ даёт нам 1+|Aᵢ| новых вариантов, где |A| - мощность (кол-во элементов) множества A.
    Т.о. ответ: ∏(1+|Aᵢ|)

    Учтите, что эта формула учитывает так же и единственный вариант выбрать 0 элементов (результат - пустое множество), соот-но от того, что вы посчитали в вопросе отличается на единицу (36 вместо 35).
    Ответ написан
  • Сколько чисел, не превосходящих 240, которые не делятся ни на 2, ни на 3, ни на 5?

    Посчитать те, которые делятся хотя бы на одно. При этом надо учитывать, что некоторые числа будут посчитаны несколько раз. Надо воспользоваться формулой включений-исключений.
    Итого делящихся хотя бы на одно из этих чисел:
    240/2 + 240/3 + 240/5 - 240/(2*3) - 240/(2*5) - 240/(3*5) + 240/(2*3*5) = 176
    Значит, неделящихся 240 - 176 = 64

    Проверяем:
    ghci> length $ filter (\x -> 0 `notElem` [x `mod` 2, x `mod` 3, x `mod` 5]) [1..240]
    64
    Ответ написан
    Комментировать
  • Как сделать перебор всех возможных комбинаций из символов?

    Напрашивается вариант представить результирующие строки записями в N-ричной системе счисления, где заданные буквы есть цифры от 0 до N-1, тогда задача сводится к выводу однозначных чисел от 0 до N-1, двузначных от 0 до N²-1, трёхзначных от 0 до N³-1. Запись в N-ричной системе легко получить, используя остаток от деления и деление.

    #include <vector>
    
    std::string gen(std::vector<char> alphabet, std::size_t idx, std::size_t digits)
    {
    	std::string ret(digits, alphabet[0]);
    
    	std::size_t alphas = alphabet.size();
    	while (digits--)
    	{
    		ret[digits] = alphabet[idx % alphas];
    		idx /= alphas;
    	}
    	return ret;
    }
    
    void gen_and_out(std::size_t n, std::vector<char> alphabet)
    {
    	std::size_t numbers = 1;
    	std::size_t alphas = alphabet.size();
    	for (std::size_t i = 0; i < n; ++i)
    	{
    		numbers *= alphas; // на каждом шаге чисел в alphas раз больше
    		for (std::size_t cur = 0; cur < numbers; ++cur)
    		{
    			std::cout << gen(alphabet, cur, i + 1) << std::endl;
    		}
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	gen_and_out(3, std::vector<char>({ 'a', 'b', 'c'}));
    }


    Второй вариант - это представить эти строки как запись числа в особой системе счисления без нуля - с цифрами от 1 до N. В этом случае легко преобразовать такую запись в число - ∑aᵢ×Nⁱ, а вот обратное преобразование должно учитывать, что у нас нет нуля, тогда если остаток получился равным нулю, цифру нужно взять N.
    В отличие от первого варианта, здесь нет отдельных циклов для однозначной, двузначной и трёхзначных записей, так как результаты идут подряд, за "c" следует "aa", за "cc" - "aaa", и так далее.

    #include <vector>
    
    std::string gen(std::vector<char> alphabet, std::size_t idx)
    {
    	std::vector<char> ret;
    
    	std::size_t alphas = alphabet.size();
    
    	while (idx)
    	{
    		std::size_t cur = idx % alphas;
    		if (!cur) // нет нуля
    			cur = alphas;
    		ret.push_back(alphabet[cur - 1]);
    		idx = (idx - cur) / alphas;
    	}
    
    	return std::string(ret.rbegin(), ret.rend());
    }
    
    void gen_and_out(std::size_t n, std::vector<char> alphabet)
    {
    	std::size_t numbers = 1;
    	std::size_t alphas = alphabet.size();
    	for (std::size_t i = 0; i < n; ++i)
    	{
    		numbers *= alphas;
    		numbers += 1;
    	}
    	for (std::size_t i = 1; i < numbers; ++i)
    		std::cout << gen(alphabet, i) << std::endl;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	gen_and_out(3, std::vector<char>({ 'a', 'b', 'c' }));
    }


    На закуску, как та же задача решается на Haskell:
    gen alphas n = concatMap (`replicateM` alphas) [1..n]
    main = mapM_ putStrLn $ gen "abc" 3
    Ответ написан
    Комментировать