Программа C, чтобы найти количество функций on и отобразить все функции

Мне нужно написать программу на C (для моего задания по дискретной математике), которая находит количество онто-функций из набора A (|A| = m) в набор B (|B|=n) и отображает все эти функции. Количество онто-функций, которые я вычислил с помощью кода:

for(k=0; k<n; k++)
    x = x + pow( -1, k) * combination( n, n - k ) * pow( ( n - k ), m);

Где комбинация — это функция, которая находит количество возможных комбинаций.

Например, если A = {1,2,3}, B={a,b,c}, то количество онто-функций, вычисляемых по формуле, равно 3^3 - 3(2^3) + 3 = 6. Один из возможных решение f = {(1,a),(2,b),(3,c)} [я знаю, что это решение].

Но моя проблема: как отобразить каждое решение!? Это просто тривиальный пример. Но если значения m и n увеличиваются (при условии, что m>=n), то количество возможных on-функций увеличивается экспоненциально!! Например, если m=7 и n=4, получается 8400 функций!

Я не могу придумать никакого метода для отображения каждой функции, существующей между A и B.


c recursion algorithm discrete-mathematics
person user    schedule 25.11.2012    source источник
comment
Не очень понятно, о чем вы спрашиваете. Возможно, возьмем очень маленький пример и покажем, что вы пытаетесь сделать, а затем пойдете дальше?   -  person PearsonArtPhoto    schedule 25.11.2012
comment
Имейте в виду, что не все здесь изучают дискретную математику, и даже большинство из них уже давно. Вы действительно должны попытаться объяснить, как делать что-то довольно простыми словами...   -  person PearsonArtPhoto    schedule 25.11.2012
comment
учитывая два набора A и B, мне нужно найти и отобразить каждую функцию от A до B. Возьмем пример: A={1,2,3} B={a,b} количество функций равно 2^3- 2=6. Мне нужно отобразить все 6 функций, которые могут существовать от А до Б в виде упорядоченных пар. f1={(1,a),(2,b),(3,b)} f2={(1,b),(2,a),(3,b)} f3={(1,b) ,(2,b),(3,a)} и так далее. Мне нужно написать код C для отображения всех этих функций.   -  person user    schedule 25.11.2012
comment
Мужчина! Если наборы не маленькие, то скоро будет много функций.   -  person dmckee --- ex-moderator kitten    schedule 25.11.2012
comment
Функция f:A->B вызывается, если f(A) = B, т.е. если для всех bEB существует хотя бы один aEA с f(a) = b   -  person user    schedule 25.11.2012
comment
Мне нужно показать образцы результатов учителю. Так что скорее всего он будет просить по тривиальным делам. Мне нужно написать функцию для отображения на функции для тривиальных случаев.   -  person user    schedule 25.11.2012
comment
сколько комбинаций для 4 цифр и 4 букв?   -  person Alberto Bonsanto    schedule 25.11.2012
comment
Для m = 4 и n = 4 есть 4 ^ 4 - 4 (3 ^ 4) + 6 (2 ^ 4) - 4 (1 ^ 4) = 24 функции   -  person user    schedule 30.11.2012

Ответы (1)


arrow_upward
4
arrow_downward

Я ответил на аналогичную проблему некоторое время назад, но m и n были равны m = n. (Вы должны думать рекурсивно, чтобы решить это), по вашему комментарию я думаю, что возможные ответы: {(1,a)(2,b)(3,c)}, {(2,a)(3,b)(1,c)}, {(3,a)(1,b)(2,c)}, {(3,a)(2,b)(1,c)}, {(2,a)(1,b)(3,c)} and {(1,a)(3,b)(2,c)} тогда это мой рецепт:

  1. Установите 2 массива с их начальным значением, назовем их letters и numbers.

    *---*---*---*                          *---*---*---*
| a | b | c | <---letters.             | 1 | 2 | 3 | <---numbers.
*---*---*---*                          *---*---*---*

  2. Выберите один из массивов в качестве опорного, я выбрал letters, он будет статическим.

    *---*---*---*                          *---*---*---*
| a | b | c | <---STATIC.              | 1 | 2 | 3 | <---DYNAMIC.
*---*---*---*                          *---*---*---*

  3. Вращайте динамический массив против или по часовой стрелке по своему усмотрению, вы должны напечатать i element of numbers с i element of letters.

    *---*---*---*               *---*---*---*                 *---*---*---* 
| 1 | 2 | 3 |   -(Print)->  | 2 | 3 | 1 |    -(Print)->   | 3 | 1 | 2 |
*---*---*---*               *---*---*---*                 *---*---*---*

Таким образом, вы получаете в этот момент: {(1,a)(2,b)(3,c)}, {(2,a)(3,b)(1,c)}, {(3,a)(1,b)(2,c)}, 3 отсутствуют.

  1. Поменяйте местами i element с n element динамического массива.

    *---*---*---*                                     *---*---*---*
| 1 | 2 | 3 |   ---------( Swap (0<->2) )-------> | 3 | 2 | 1 | 
*---*---*---*                                     *---*---*---*

  2. Повторите шаг 3.

    *---*---*---*               *---*---*---*                 *---*---*---* 
| 3 | 2 | 1 |   -(Print)->  | 2 | 1 | 3 |    -(Print)->   | 1 | 3 | 2 |
*---*---*---*               *---*---*---*                 *---*---*---*

Таким образом, вы получаете пропущенные подмножества: {(3,a)(2,b)(1,c)}, {(2,a)(1,b)(3,c)} and {(1,a)(3,b)(2,c)}.

Если у вас больше 3-х, пример 4. Легко: 1234 (повернуть N раз, где N — количество переменных и печатать при каждом движении), поменять местами 1 и 4 -> 4231 (повернуть и напечатать), поменять местами 2 и 3 -> 4321 (Повернуть и распечатать), поменять местами 4 и 1 --> 1324 (Повернуть и распечатать).

Надеюсь, это помогло.

person Alberto Bonsanto    schedule 25.11.2012
comment
Если вы ответите на вопрос домашнего задания без публикации кода для вставки, вы автоматически получите от меня +1. - person sbi; 26.11.2012