技术宅的结界

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

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 183|回复: 0
收起左侧

【C】计算排列组合

[复制链接]

7

主题

11

帖子

261

积分

用户组: 中·技术宅

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

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

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

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

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

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

int cbfcmp(const void * px, const void * py)
{
	return *(char *)px - *(char *)py;
}

int main(void)
{
	auto char c;
	ARRAY_Z arrz; // 使用一个数组
	strInitArrayZ(&arrz, 3, sizeof(char)); // 初始化数组
	memcpy(arrz.pdata, "123", 3); // 将数组设置为1、2、3
	do
	{
		strTraverseArrayZ(&arrz, sizeof(char), cbftvs, 0, FALSE); // 打印数组
		printf("\n");
	} while (strPermuteArrayZ(&arrz, &c, sizeof(char), cbfcmp, TRUE)); // 按字典序对数组进行排列
	strFreeArrayZ(&arrz); // 释放数组
	return 0;
}

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

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

int cbfcmp(const void * px, const void * py)
{
	return *(char *)px - *(char *)py;
}

int main(void)
{
	auto char c;
	ARRAY_Z arrz, arrb; // 使用数组
	strInitArrayZ(&arrz, 3, sizeof(char)); // 初始化数组
	strInitArrayZ(&arrb, 4, sizeof(char));
	memcpy(arrz.pdata, "123", 3); // 将数组设置为1、2、3就是字典序的第一个组合
	memcpy(arrb.pdata, "1234", 4); // 将数组设置为1、2、3、4
	do
	{
		strTraverseArrayZ(&arrz, sizeof(char), cbftvs, 0, FALSE); // 打印数组
		printf("\n");
	} while (strCombineNextArrayZ(&arrz, &arrb, sizeof(char), cbfcmp)); // 按字典序计算arrb数组的组合
	strFreeArrayZ(&arrz); // 释放数组
	strFreeArrayZ(&arrb);
	return 0;
}

        计算结果:
1 2 3
1 2 4
1 3 4
2 3 4
下面是一个计算排列组合的综合例子:
[C] 纯文本查看 复制代码
#include <stdio.h>
#include <string.h>
#include "..\\src\\svstring.h"

#define N_ 4
#define R_ 3
#define strize(a) # a
#define numerize(s) strize(s)
#define paste(a, b, c) a ## b ## c

typedef char MYTYPE;

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

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

// Function: main
// Desc:     Program entry.
// Param:    N/A.
// Return:   0: no error; 1, 2: allocation failure.
int main(void)
{
	char q;
	int i = 0;
	ARRAY_Z n, r;
	char pstr[] = "abcd", t;
	/* Initialize two arrays. */
	if (NULL == strInitArrayZ(&n, N_, sizeof(MYTYPE)))
		return 1; /* Allocation failure. */
	if (NULL == strInitArrayZ(&r, R_, sizeof(MYTYPE)))
	{	/* Another alocation failure. */
		i = 2;
		goto Lbl_Bad_Allocation;
	}
	/* Initialize two arrays. */
	memcpy(n.pdata, pstr, N_ * sizeof(MYTYPE));
	memcpy(r.pdata, pstr, R_ * sizeof(MYTYPE));
	do
		fflush(stdin), printf("Would you like to print the result numerically(Y/n)? "), scanf("%c", &q);
	while (q != 'Y' && q != 'y' && q != 'N' && q != 'n');
	q = !(q & 1);
	printf("P(%d, %d) =\n", N_, R_);
	do
	{	/* Generate all permutations of the current subset for combination. */
		while
		(	/* Some versions of GCCs would mis-parse the following sentence while VC won't. */
			printf(paste("%", numerize(N_), "d:\t"), ++i),
			PrintArrayZ(&r, sizeof(MYTYPE), (BOOL)q),
			strPermuteArrayZ(&r, &t, sizeof(MYTYPE), cbfcmp, TRUE)
		);
	}	/* Generate (nCr) circularly. */
	while (strCombineNextArrayZ(&r, &n, sizeof(MYTYPE), cbfcmp));
	i = 0;
	strFreeArrayZ(&r);
Lbl_Bad_Allocation:
	strFreeArrayZ(&n);
	return i;
}

        运行结果如下:
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库中节选出来抄在下边:
[C] 纯文本查看 复制代码
/* Function name: strPermuteArrayZ
 * Description:   Permute a fixed size array in dictionary order.
 * Parameters:
 *      parrz Pointer to a sized array.
 *      ptemp Pointer to a buffer whose size equals to each size of the element in the array.
 *       size Size of each element in the array.
 *     cbfcmp Pointer to a function that compares any two elements in array.
 *      bnext Input TRUE to permute an array next; Input FALSE to permute an array previously.
 * Return value:  TRUE indicates permutation continued; FALSE indicates permutation ended.
 * Caution:       Address of parrz Must Be Allocated first.
 *                Users shall manage the buffer that ptemp points at.
 *                (*) The size of the buffer of ptemp pointed shall equal to parameter size.
 *                (*) Each element in the array shall be unique.
 * Tip:           Users may call strUniqueArrayZ to generate a suitable array for permuting.
 *                This function references to two similar templates in STL of C Plus Plus.
 */
BOOL strPermuteArrayZ(P_ARRAY_Z parrz, void * ptemp, size_t size, CBF_COMPARE cbfcmp, BOOL bnext)
{
	if (strLevelArrayZ(parrz) > 1 && size > 0) /* Worth permuting. */
	{	/* ptrl Always points the last element. */
		REGISTER PUCHAR ptrl = parrz->pdata + (strLevelArrayZ(parrz) - 1) * size;
		REGISTER PUCHAR ptri, ptrj;
		for (ptri = ptrl - size, ptrj = ptrl;; ptri -= size, ptrj -= size)
		{
			REGISTER int r = cbfcmp(ptri, ptrj);
			if (bnext ? r < 0 : r > 0)
			{
				REGISTER PUCHAR ptrk;
				for
				(
					ptrk = ptrl;
					(r = cbfcmp(ptrk, ptri)),
					!(bnext ? r > 0 : r < 0);
					ptrk -= size
				);
				/* Swap (*i) and (*k). */
				svSwap(ptri, ptrk, ptemp, size);
				{	/* Reverse array from j to last. */
					ARRAY_Z arrt; /* Auxiliary array header for reversing. */
					arrt.num   = (size_t)((ptrl - ptrj) / size + 1);
					arrt.pdata = ptrj;
					strReverseArrayZ(&arrt, ptemp, size);
				}
				return TRUE;
			}
			if (ptri <= parrz->pdata)
			{	/* Reverse array from first to last. */
				strReverseArrayZ(parrz, ptemp, size);
				goto Lbl_End_Permuting;
			}
		}
	}
Lbl_End_Permuting:
	return FALSE;
}

/* Function name: strCombineNextArrayZ
 * Description:   Generate the next combination of an array in dictionary order.
 *                If n equaled (parrzn->num) and r equaled (parrzr->num), this function would generate
 *                the subset r of parrzn aka (n C r) aka C(n, r) and finally copy the result into parrzr.
 * Parameters:
 *     parrzr Pointer to an initialized array that contains a result of a previous combination.
 *     parrzn Pointer to a sized array that is sorted in increasing order.
 *       size Size of each element in both two arrays.
 *     cbfcmp Pointer to a function that compares any two elements in two arrays.
 * Return value:  TRUE indicates combination continued; FALSE indicates combination ended.
 * Caution:       Address of Both parrzn and parrzr Must Be Allocated first.
 *                (*) Each element in parrzn shall be unique.
 *                (*) Elements in array that parrzn and parrzr pointed shall be sorted in increasing order.
 * Tip:           Users may call strUniqueArrayZ(parrzn, ptemp, size, cbfcmp, TRUE);
 *                to generate a suitable array for combination.
 */
BOOL strCombineNextArrayZ(P_ARRAY_Z parrzr, P_ARRAY_Z parrzn, size_t size, CBF_COMPARE cbfcmp)
{	/* Assume that the array that parrzn contains has been assigned and sorted yet. */
	if (parrzr->num > 0 && parrzr->num < parrzn->num)
	{
		REGISTER size_t i, j = parrzr->num - 1;
		REGISTER PUCHAR pa = &parrzr->pdata[size * j];
		REGISTER PUCHAR pt = &parrzn->pdata[size * (parrzn->num - 1)];
		/* Compare back through parrzn with parrzr to find a position as pa. */
		for (i = 0; i < j; ++i, pt -= size, pa -= size)
			if (0 != cbfcmp(pt, pa))
				break;
		if (0 == cbfcmp(pt, pa))
			goto Lbl_End_Combination; /* Combination reaches at the end. */
		if (NULL == (pt = (PUCHAR) svBinarySearch(pa, parrzn->pdata, parrzn->num, size, cbfcmp)))
			goto Lbl_End_Combination; /* An element in parrzr doesn't match any element in parrzn. */
		/* Fill subset r with values in parrzn. */
		pt += size;
		i = parrzr->num - (pa - parrzr->pdata + size) / size;
		do
		{
			memcpy(pa, pt, size);
			pa += size;
			pt += size;
		}
		while (0 != i--);
		return TRUE;
	}
Lbl_End_Combination:
	return FALSE; /* No next combination. */
}

评分

参与人数 1威望 +5 宅币 +10 贡献 +10 收起 理由
0xAA55 + 5 + 10 + 10 StoneValley库,我第一次听说

查看全部评分

本帖被以下淘专辑推荐:

回复

使用道具 举报

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图  

GMT+8, 2020-11-28 04:47 , Processed in 0.097656 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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