c - 関数の数を見つけてすべての関数を表示する C プログラム

Question

A (|A| = m)セットからセットへの関数の数を見つけ、B (|B|=n)それらすべての関数を表示する C プログラムを (離散数学の割り当てのために) 作成する必要があります。コードを使用して計算した関数の数:

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} の場合、式から評価される on 関数の数は 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の間に存在するすべての関数を表示する方法は考えられません。

Answer 1

私は以前に同様の問題に答えましたが、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. ピボットにする配列の 1 つを選択します。私は を選択しました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)}.

例 4 が31234つ以上ある場合。印刷)、4 と 1 を交換 --> (回転して印刷)。423143211324

これが役に立ったことを願っています。