找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 4346|回复: 1

【C】计算排列组合

[复制链接]

17

主题

41

回帖

764

积分

用户组: 大·技术宅

UID
6266
精华
6
威望
58 点
宅币
510 个
贡献
50 次
宅之契约
0 份
在线时间
41 小时
注册时间
2020-9-26
发表于 2020-11-2 21:48:19 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
本帖最后由 new_starter 于 2020-11-2 21:52 编辑

下面将给大家演示怎样使用StoneValley库计算排列组合:
1.计算排列:
        以下代码按字典序计算1、2、3的全排列:
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "StoneValley-master/src/svstring.h"

  4. int cbftvs(void * pitem, size_t param)
  5. {
  6.         printf(" %c", *(char *)pitem); // 打印数组中的每个元素
  7.         return CBF_CONTINUE;
  8. }

  9. int cbfcmp(const void * px, const void * py)
  10. {
  11.         return *(char *)px - *(char *)py;
  12. }

  13. int main(void)
  14. {
  15.         auto char c;
  16.         ARRAY_Z arrz; // 使用一个数组
  17.         strInitArrayZ(&arrz, 3, sizeof(char)); // 初始化数组
  18.         memcpy(arrz.pdata, "123", 3); // 将数组设置为1、2、3
  19.         do
  20.         {
  21.                 strTraverseArrayZ(&arrz, sizeof(char), cbftvs, 0, FALSE); // 打印数组
  22.                 printf("\n");
  23.         } while (strPermuteArrayZ(&arrz, &c, sizeof(char), cbfcmp, TRUE)); // 按字典序对数组进行排列
  24.         strFreeArrayZ(&arrz); // 释放数组
  25.         return 0;
  26. }
复制代码

        计算结果:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
2.计算组合:
        以下代码按字典序计算1、2、3、4中任意取出3个的组合:
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "StoneValley-master/src/svstring.h"

  4. int cbftvs(void * pitem, size_t param)
  5. {
  6.         printf(" %c", *(char *)pitem); // 打印数组中的每个元素
  7.         return CBF_CONTINUE;
  8. }

  9. int cbfcmp(const void * px, const void * py)
  10. {
  11.         return *(char *)px - *(char *)py;
  12. }

  13. int main(void)
  14. {
  15.         auto char c;
  16.         ARRAY_Z arrz, arrb; // 使用数组
  17.         strInitArrayZ(&arrz, 3, sizeof(char)); // 初始化数组
  18.         strInitArrayZ(&arrb, 4, sizeof(char));
  19.         memcpy(arrz.pdata, "123", 3); // 将数组设置为1、2、3就是字典序的第一个组合
  20.         memcpy(arrb.pdata, "1234", 4); // 将数组设置为1、2、3、4
  21.         do
  22.         {
  23.                 strTraverseArrayZ(&arrz, sizeof(char), cbftvs, 0, FALSE); // 打印数组
  24.                 printf("\n");
  25.         } while (strCombineNextArrayZ(&arrz, &arrb, sizeof(char), cbfcmp)); // 按字典序计算arrb数组的组合
  26.         strFreeArrayZ(&arrz); // 释放数组
  27.         strFreeArrayZ(&arrb);
  28.         return 0;
  29. }
复制代码

        计算结果:
1 2 3
1 2 4
1 3 4
2 3 4
下面是一个计算排列组合的综合例子:
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "..\\src\\svstring.h"

  4. #define N_ 4
  5. #define R_ 3
  6. #define strize(a) # a
  7. #define numerize(s) strize(s)
  8. #define paste(a, b, c) a ## b ## c

  9. typedef char MYTYPE;

  10. // Function: cbfcmp
  11. // Desc:     Compare values for MYTYPE values.
  12. // Param:    px: a pointer to a MYTYPE value. py: a pointer to another MYTYPE value.
  13. // Return:   Either 1, -1 or 0 depends on comparison result.
  14. int cbfcmp(const void * px, const void * py)
  15. {
  16.         if (*(MYTYPE *)px > *(MYTYPE *)py) return  1;
  17.         if (*(MYTYPE *)px < *(MYTYPE *)py) return -1;
  18.         return 0;
  19. }

  20. // Function: PrintArrayZ
  21. // Desc:     Print data for an sized array from index 0 to (n - 1).
  22. // Param:    parrz:  pointer to a sized array.
  23. //           n:      Number of items you want to print.
  24. //           size:   Size of each element in the array.
  25. //           bchar:  TRUE: print char; FALSE: print number.
  26. // Return:   N/A.
  27. void PrintArrayZ(P_ARRAY_Z parrz, size_t size, BOOL bchar)
  28. {
  29.         char c;
  30.         size_t i;
  31.         /* Hide a private member by using a macro or a function is not elegant,
  32.          * Therefore we cannot use classes in C, this is a better way to circumvent
  33.          * altering parrz->num, so that strLevelArrayZ might not be an appendix.
  34.          */
  35.         for (i = 0; i < strLevelArrayZ(parrz); ++i)
  36.                 printf("%c", (c = *(MYTYPE *)(parrz->pdata + i * size), bchar ? c : c - '0'));
  37.         printf("\n");
  38. }

  39. // Function: main
  40. // Desc:     Program entry.
  41. // Param:    N/A.
  42. // Return:   0: no error; 1, 2: allocation failure.
  43. int main(void)
  44. {
  45.         char q;
  46.         int i = 0;
  47.         ARRAY_Z n, r;
  48.         char pstr[] = "abcd", t;
  49.         /* Initialize two arrays. */
  50.         if (NULL == strInitArrayZ(&n, N_, sizeof(MYTYPE)))
  51.                 return 1; /* Allocation failure. */
  52.         if (NULL == strInitArrayZ(&r, R_, sizeof(MYTYPE)))
  53.         {        /* Another alocation failure. */
  54.                 i = 2;
  55.                 goto Lbl_Bad_Allocation;
  56.         }
  57.         /* Initialize two arrays. */
  58.         memcpy(n.pdata, pstr, N_ * sizeof(MYTYPE));
  59.         memcpy(r.pdata, pstr, R_ * sizeof(MYTYPE));
  60.         do
  61.                 fflush(stdin), printf("Would you like to print the result numerically(Y/n)? "), scanf("%c", &q);
  62.         while (q != 'Y' && q != 'y' && q != 'N' && q != 'n');
  63.         q = !(q & 1);
  64.         printf("P(%d, %d) =\n", N_, R_);
  65.         do
  66.         {        /* Generate all permutations of the current subset for combination. */
  67.                 while
  68.                 (        /* Some versions of GCCs would mis-parse the following sentence while VC won't. */
  69.                         printf(paste("%", numerize(N_), "d:\t"), ++i),
  70.                         PrintArrayZ(&r, sizeof(MYTYPE), (BOOL)q),
  71.                         strPermuteArrayZ(&r, &t, sizeof(MYTYPE), cbfcmp, TRUE)
  72.                 );
  73.         }        /* Generate (nCr) circularly. */
  74.         while (strCombineNextArrayZ(&r, &n, sizeof(MYTYPE), cbfcmp));
  75.         i = 0;
  76.         strFreeArrayZ(&r);
  77. Lbl_Bad_Allocation:
  78.         strFreeArrayZ(&n);
  79.         return i;
  80. }
复制代码

        运行结果如下:
Would you like to print the result numerically(Y/n)? n
P(4, 3) =
   1:   abc
   2:   acb
   3:   bac
   4:   bca
   5:   cab
   6:   cba
   7:   abd
   8:   adb
   9:   bad
  10:   bda
  11:   dab
  12:   dba
  13:   acd
  14:   adc
  15:   cad
  16:   cda
  17:   dac
  18:   dca
  19:   bcd
  20:   bdc
  21:   cbd
  22:   cdb
  23:   dbc
  24:   dcb
排列组合的关键是调用了strPermuteArrayZ和strCombineNextArrayZ函数,下面将俩函数从StoneValley库中节选出来抄在下边:
  1. /* Function name: strPermuteArrayZ
  2. * Description:   Permute a fixed size array in dictionary order.
  3. * Parameters:
  4. *      parrz Pointer to a sized array.
  5. *      ptemp Pointer to a buffer whose size equals to each size of the element in the array.
  6. *       size Size of each element in the array.
  7. *     cbfcmp Pointer to a function that compares any two elements in array.
  8. *      bnext Input TRUE to permute an array next; Input FALSE to permute an array previously.
  9. * Return value:  TRUE indicates permutation continued; FALSE indicates permutation ended.
  10. * Caution:       Address of parrz Must Be Allocated first.
  11. *                Users shall manage the buffer that ptemp points at.
  12. *                (*) The size of the buffer of ptemp pointed shall equal to parameter size.
  13. *                (*) Each element in the array shall be unique.
  14. * Tip:           Users may call strUniqueArrayZ to generate a suitable array for permuting.
  15. *                This function references to two similar templates in STL of C Plus Plus.
  16. */
  17. BOOL strPermuteArrayZ(P_ARRAY_Z parrz, void * ptemp, size_t size, CBF_COMPARE cbfcmp, BOOL bnext)
  18. {
  19.         if (strLevelArrayZ(parrz) > 1 && size > 0) /* Worth permuting. */
  20.         {        /* ptrl Always points the last element. */
  21.                 REGISTER PUCHAR ptrl = parrz->pdata + (strLevelArrayZ(parrz) - 1) * size;
  22.                 REGISTER PUCHAR ptri, ptrj;
  23.                 for (ptri = ptrl - size, ptrj = ptrl;; ptri -= size, ptrj -= size)
  24.                 {
  25.                         REGISTER int r = cbfcmp(ptri, ptrj);
  26.                         if (bnext ? r < 0 : r > 0)
  27.                         {
  28.                                 REGISTER PUCHAR ptrk;
  29.                                 for
  30.                                 (
  31.                                         ptrk = ptrl;
  32.                                         (r = cbfcmp(ptrk, ptri)),
  33.                                         !(bnext ? r > 0 : r < 0);
  34.                                         ptrk -= size
  35.                                 );
  36.                                 /* Swap (*i) and (*k). */
  37.                                 svSwap(ptri, ptrk, ptemp, size);
  38.                                 {        /* Reverse array from j to last. */
  39.                                         ARRAY_Z arrt; /* Auxiliary array header for reversing. */
  40.                                         arrt.num   = (size_t)((ptrl - ptrj) / size + 1);
  41.                                         arrt.pdata = ptrj;
  42.                                         strReverseArrayZ(&arrt, ptemp, size);
  43.                                 }
  44.                                 return TRUE;
  45.                         }
  46.                         if (ptri <= parrz->pdata)
  47.                         {        /* Reverse array from first to last. */
  48.                                 strReverseArrayZ(parrz, ptemp, size);
  49.                                 goto Lbl_End_Permuting;
  50.                         }
  51.                 }
  52.         }
  53. Lbl_End_Permuting:
  54.         return FALSE;
  55. }

  56. /* Function name: strCombineNextArrayZ
  57. * Description:   Generate the next combination of an array in dictionary order.
  58. *                If n equaled (parrzn->num) and r equaled (parrzr->num), this function would generate
  59. *                the subset r of parrzn aka (n C r) aka C(n, r) and finally copy the result into parrzr.
  60. * Parameters:
  61. *     parrzr Pointer to an initialized array that contains a result of a previous combination.
  62. *     parrzn Pointer to a sized array that is sorted in increasing order.
  63. *       size Size of each element in both two arrays.
  64. *     cbfcmp Pointer to a function that compares any two elements in two arrays.
  65. * Return value:  TRUE indicates combination continued; FALSE indicates combination ended.
  66. * Caution:       Address of Both parrzn and parrzr Must Be Allocated first.
  67. *                (*) Each element in parrzn shall be unique.
  68. *                (*) Elements in array that parrzn and parrzr pointed shall be sorted in increasing order.
  69. * Tip:           Users may call strUniqueArrayZ(parrzn, ptemp, size, cbfcmp, TRUE);
  70. *                to generate a suitable array for combination.
  71. */
  72. BOOL strCombineNextArrayZ(P_ARRAY_Z parrzr, P_ARRAY_Z parrzn, size_t size, CBF_COMPARE cbfcmp)
  73. {        /* Assume that the array that parrzn contains has been assigned and sorted yet. */
  74.         if (parrzr->num > 0 && parrzr->num < parrzn->num)
  75.         {
  76.                 REGISTER size_t i, j = parrzr->num - 1;
  77.                 REGISTER PUCHAR pa = &parrzr->pdata[size * j];
  78.                 REGISTER PUCHAR pt = &parrzn->pdata[size * (parrzn->num - 1)];
  79.                 /* Compare back through parrzn with parrzr to find a position as pa. */
  80.                 for (i = 0; i < j; ++i, pt -= size, pa -= size)
  81.                         if (0 != cbfcmp(pt, pa))
  82.                                 break;
  83.                 if (0 == cbfcmp(pt, pa))
  84.                         goto Lbl_End_Combination; /* Combination reaches at the end. */
  85.                 if (NULL == (pt = (PUCHAR) svBinarySearch(pa, parrzn->pdata, parrzn->num, size, cbfcmp)))
  86.                         goto Lbl_End_Combination; /* An element in parrzr doesn't match any element in parrzn. */
  87.                 /* Fill subset r with values in parrzn. */
  88.                 pt += size;
  89.                 i = parrzr->num - (pa - parrzr->pdata + size) / size;
  90.                 do
  91.                 {
  92.                         memcpy(pa, pt, size);
  93.                         pa += size;
  94.                         pt += size;
  95.                 }
  96.                 while (0 != i--);
  97.                 return TRUE;
  98.         }
  99. Lbl_End_Combination:
  100.         return FALSE; /* No next combination. */
  101. }
复制代码

本帖被以下淘专辑推荐:

回复

使用道具 举报

1

主题

3

回帖

17

积分

用户组: 初·技术宅

UID
6729
精华
0
威望
6 点
宅币
1 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2021-3-11
发表于 2021-3-11 03:27:29 | 显示全部楼层
谢谢大佬的思路
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 03:38 , Processed in 0.035401 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表