C语言实现排列组合的经典应用（例如：0,1,2元素共有0；1；2；01；02；12；012 （2^3-1中组合））

2019.11.26

一背景：

老板心血来潮找来C试题试试我们的深浅，Google 原题源于某论坛但暂时未解答，排列组合算法实现是关键，通过大佬指导，利用C语言排列组合实现。

二题目要求

原题目要求
题目解释：程序要求输入行数1-100和列数1-10 的数组（数组元素为0或1），每次只翻动一行或者一列，即不允许翻动单个元素，使得最终数组中的1最多。

example：
输入输出举例
三. C语言实现思路

开发环境visual studio 2017：
1.单行单列翻转容易处理，0多余1翻转，反之不翻转。
2.多行多列比较麻烦，开始认为只翻转0多余1的行和列就可以，但是发现0和1相等或者1多余0的行列的翻转会互相影响，有的组合翻转可以使得1的个数增加，所以不能简单考虑，必须组合翻转判断是否可取。

四. Source code

1.C语言排列组合测试code，可以用两个for循环实现。

//Source code
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int array[3] = { 0,1,2 };
	int count = 3;
	int i, j;

	for (i = 1; i < (1 << count); i++)
	{
		printf("jeet test loop =%d\n", i);
		for (j = 0; j < count; j++)
		{			
			if (i & (1 << j))
			{
				printf("jeet test array[j]=%d\n", array[j]);
			}
		}
	}
	return 0;
}
#endif

测试log

jeet test loop =1
jeet test array[j]=0
jeet test loop =2
jeet test array[j]=1
jeet test loop =3
jeet test array[j]=0
jeet test array[j]=1
jeet test loop =4
jeet test array[j]=2
jeet test loop =5
jeet test array[j]=0
jeet test array[j]=2
jeet test loop =6
jeet test array[j]=1
jeet test array[j]=2
jeet test loop =7
jeet test array[j]=0
jeet test array[j]=1
jeet test array[j]=2

G:\little_fish\fish_c_lesson\jeet_c_practise\2019_1119\coinFliping\coinFliping\Debug\coinFliping.exe (进程 7696)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口...

2. 题目实现source code

//source code
//coin flipping easy game
//Author: Jeet.Liu
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <math.h>
#define DEBUG_LOG 0

int rows, columns;
int* rowequalArray;
int* columnequalArray;
int* coinArray;
int* backcoinArray;
int* tempcoinArray;

void dataCheck(void);
void rowTrans(int rowtransNum);
void columnTrans(int columntransNum);
int rowSum(int rowsumNum);
int columnSum(int columnsumNum);
int rowabsSum(void);
int columnabsSum(void);
int rowandcoluSum(void);
int inputInteger(const char* prompt, int max, int min);
void inputArray(int* tempArr, int tempRow, int tempColumn);
void outputArray(int* tempArr, int tempRow, int tempColumn);
void arrayConvert(int* tempArr, int tempRow, int tempColumn);
void arrayRestore(int* tempArr, int tempRow, int tempColumn);
void onelineTrans(int* tempArr, int tempRow, int tempColumn);

int main()
{
	int i, j;
	rows = inputInteger("行数 请输入1~100之间的整数:", 100, 1);
	printf("用户输入的行数是：%d\n", rows);
	columns = inputInteger("列数 请输入1~10之间的整数:", 10, 1);
	printf("用户输入的列数是：%d\n", columns);

//动态分配内存
	coinArray = (int *)malloc(sizeof(int) * rows * columns);//二维数组一次性分配内存
	rowequalArray = (int *)malloc(sizeof(int) * rows);
	columnequalArray = (int *)malloc(sizeof(int) * columns);
	backcoinArray = (int *)malloc(sizeof(int) * rows * columns);
	tempcoinArray = (int *)malloc(sizeof(int) * rows * columns);
	//笔误内存分配不够溢出
	
//自动输入数组测试：
#if 1
	srand((unsigned)time(NULL));//srand()就是给rand()提供种子seed 

	for (i = 0; i < rows; i++)
	{
		for (j = 0; j < columns; j++)
		{
			*((coinArray + i * columns) + j) = rand() % 2;//对2取余得到就是0或者1		
		}
	}
#endif

//手动输入数组测试：
//inputArray(coinArray, rows, columns);

	printf("输入的数列是：\n");
	outputArray(coinArray, rows, columns);

//数组元素0转换-1	
	arrayConvert(coinArray, rows, columns);
	dataCheck();
//数组元素转换0
	arrayRestore(coinArray, rows, columns);
//转换后输出测试
	printf("转换后的数列是：\n");
	outputArray(coinArray, rows, columns);

//释放动态开辟的空间
	free(coinArray);
	free(rowequalArray);
	free(columnequalArray);
	free(backcoinArray);
	free(tempcoinArray);

	return 0;
}

//输入检查函数：
int inputInteger(const char* prompt, int max, int min)

{
	int result = 0;
	int inputCount = 0;

	do
	{
		printf("%s", prompt);
		rewind(stdin);
		inputCount = scanf_s("%d", &result);

	} while (inputCount == 0 || result > max || result < min);

	return result;
}

void inputArray(int* tempArr, int tempRow, int tempColumn)
{
	int i;
	int j;
	int countColumns = 0;
	countColumns = tempColumn;
	for (i = 0; i < tempRow; i++)
	{
		for (j = 0; j < tempColumn; j++)
		{

			printf("tempArr[%d][%d]=", i, j);
			*((tempArr + i * countColumns) + j) = inputInteger(" ", 1, 0);
		}
	}


}

void outputArray(int* tempArr, int tempRow, int tempColumn)
{
	int i;
	int j;
	int arraySum = 0;



	for (i = 0; i < tempRow; i++)
	{
		for (j = 0; j < tempColumn; j++)
		{
			arraySum += *(tempArr + i * tempColumn + j);
			printf("%d    ", *(tempArr + i * tempColumn + j));
		
		}

		printf("\n");
	}
		printf("head 最多个数为：%d\n", arraySum);

}


void dataCheck(void)
{
	int i, j, m, n;
	int oldVal = 0;
	int newVal = 0;
	int changedFlag = 0;
	int loopFlag = 0;

	int rowequalNum = 0;
	int columnequalNum = 0;

	//单行
	if (1 == rows || 1 == columns)
	{
		onelineTrans(coinArray, rows, columns);
	
	}

	//多行
	else
	{
		do
		{
			//清除循环flag
			loopFlag = 0;

			//行转换
			for (i = 0; i < rows; i++)
			{
				if (rowSum(i) < 0)
				{
					rowTrans(i);
#if DEBUG_LOG
					arrayRestore(coinArray, rows, columns);
					outputArray(coinArray, rows, columns);
					arrayConvert(coinArray, rows, columns);
#endif
					loopFlag = 1;  //有转换设flag
				}
			}
					
			rowequalNum = 0;
			changedFlag = 0;  //清flag 和计数
			
			for (i = 0; i < rows; i++)
			{
				//if (0 == rowSum(i))  //仅仅是0和1个数一样的组合
				{
					rowequalArray[rowequalNum++] = i;   //行号保存在数组中
				}

			}

			oldVal = columnabsSum();  //转换各列和的绝对值之和
			if (rowequalNum)
			{
				for (m = 1; m < (1 << rowequalNum); m++)  //排列组合
				{

					//backcoinArray = coinArray; //错误示范，指针随便用会崩掉
					memcpy(backcoinArray, coinArray, rows * columns * sizeof(int));  //备份数组


					for (n = 0; n < rowequalNum; n++)
					{
						if (m & (1 << n))
						{
							rowTrans(*(rowequalArray + n)); //转换指定行
						}
					}

					newVal = columnabsSum();//转换后各列和的绝对值之和

					if (newVal > oldVal)
					{
						oldVal = newVal;
						memcpy(tempcoinArray, coinArray, rows * columns * sizeof(int));  //保存有效转换数组
						changedFlag = 1;
					}
					memcpy(coinArray, backcoinArray, rows * columns * sizeof(int));//恢复数组
				}

				if (changedFlag)
				{
					loopFlag = 1;  //有转换设flag
					memcpy(coinArray, tempcoinArray, rows * columns * sizeof(int)); //刷新有效转换数组后输出
#if DEBUG_LOG
					arrayRestore(coinArray, rows, columns);
					outputArray(coinArray, rows, columns);
					arrayConvert(coinArray, rows, columns);
#endif
				}
			}

			//列转换

			for (j = 0; j < columns; j++)
			{
				if (columnSum(j) < 0)
				{
					columnTrans(j);
#if DEBUG_LOG
					arrayRestore(coinArray, rows, columns);
					outputArray(coinArray, rows, columns);
					arrayConvert(coinArray, rows, columns);
#endif
					loopFlag = 1;
				}

			}

			columnequalNum = 0;
			changedFlag = 0;

			for (j = 0; j < columns; j++)
			{
				//if (0 == columnSum(j)) //仅仅是0和1个数一样的组合
				{
					columnequalArray[columnequalNum++] = j;
				}
			}
			
			oldVal = rowabsSum();
			if (columnequalNum)
			{
				for (m = 1; m < (1 << columnequalNum); m++)
				{
					memcpy(backcoinArray, coinArray, rows * columns * sizeof(int));

					for (n = 0; n < columnequalNum; n++)
					{
						if (m & (1 << n))
						{
							columnTrans(*(columnequalArray + n));
						}
					}

					newVal = rowabsSum();

					if (newVal > oldVal)
					{
						oldVal = newVal;
						memcpy(tempcoinArray, coinArray, rows * columns * sizeof(int));
						changedFlag = 1;
					}
					memcpy(coinArray, backcoinArray, rows * columns * sizeof(int));
				}

				if (changedFlag)
				{
					loopFlag = 1;
					memcpy(coinArray, tempcoinArray, rows * columns * sizeof(int));
#if DEBUG_LOG
					arrayRestore(coinArray, rows, columns);
					outputArray(coinArray, rows, columns);
					arrayConvert(coinArray, rows, columns);
#endif
				}
			}
		} while (loopFlag);
	}
}


void rowTrans(int rowtransNum)
{
	int j;

	for (j = 0; j < columns; j++)
	{
		if (*(coinArray + rowtransNum * columns + j) == 1)
		{
			*(coinArray + rowtransNum * columns + j) -= 2;
		}
		else
		{
			*(coinArray + rowtransNum * columns + j) += 2;
		}
	}
}


void columnTrans(int columntransNum)
{
	int i;
	for (i = 0; i < rows; i++)
	{
		if (*(coinArray + i * columns + columntransNum) == 1)
		{
			*(coinArray + i * columns + columntransNum) -= 2;
		}
		else
		{
			*(coinArray + i * columns + columntransNum) += 2;
		}
	}
}

void onelineTrans(int* tempArr, int tempRow, int tempColumn)
{
	int i;
	int j;

	if (rowandcoluSum() < 0)
	{
		for (i = 0; i < tempRow; i++)
		{
			for (j = 0; j < tempColumn; j++)
			{
				if (1 == *(tempArr + i * tempColumn + j))
				{
					*(tempArr + i * tempColumn + j) -= 2;
				}
				else
				{
					*(tempArr + i * tempColumn + j) += 2;
				}
			}
		}
	}
}

int rowSum(int rowsumNum)
{
	int sum = 0;
	int j;
	for (j = 0; j < columns; j++)
	{
		sum += *(coinArray + rowsumNum * columns + j);
	}
	return sum;

}


int columnSum(int columnsumNum)
{
	int sum = 0;
	int i;
	for (i = 0; i < rows; i++)
	{
		sum += *(coinArray + i * columns + columnsumNum);
	}
	return sum;
}

int rowabsSum(void)
{
	int i;
	int sum = 0;
	for (i = 0; i < rows; i++)
	{
		sum += abs(rowSum(i));
	}
	return sum;
}

int columnabsSum(void)
{
	int j;
	int sum = 0;
	for (j = 0; j < columns; j++)
	{
		sum += abs(columnSum(j));
	}
	return sum;
}


int rowandcoluSum(void)
{
	int i;
	int j;
	int sum = 0;

	for (i = 0; i < rows; i++)
	{
		for (j = 0; j < columns; j++)
		{
			sum += *((coinArray + i * columns) + j);
		}	
	}
	return sum;
}


void arrayConvert(int* tempArr, int tempRow, int tempColumn)

{
	int i;
	int j;

	for (i = 0; i < tempRow; i++)
	{
		for (j = 0; j < tempColumn; j++)
		{
			if (*((tempArr + i * tempColumn) + j) == 0)
			{
				*((tempArr + i * tempColumn) + j) -= 1;
			}
		}
	}
}


void arrayRestore(int* tempArr, int tempRow, int tempColumn)

{
	int i;
	int j;

	for (i = 0; i < tempRow; i++)
	{
		for (j = 0; j < tempColumn; j++)
		{
			if (*((tempArr + i * tempColumn) + j) == -1)
			{
				*((tempArr + i * tempColumn) + j) += 1;
			}
		}
	}
}

测试log：


行数 请输入1~100之间的整数:5
用户输入的行数是：5
列数 请输入1~10之间的整数:4
用户输入的列数是：4
输入的数列是：
0    0    0    0
0    0    0    0
0    1    1    0
0    1    0    1
1    0    0    0
head 最多个数为：5
转换后的数列是：
0    1    1    1
0    1    1    1
1    1    1    0
1    1    0    1
1    1    1    1
head 最多个数为：16

G:\little_fish\fish_c_lesson\jeet_c_practise\2019_1119\coinFliping\coinFliping\Debug\coinFliping.exe (进程 8888)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口...

五.总结：

1.笔误内存动态分配空间不足造成内存溢出。


HEAP CORRUPTION DETECTED: after Normal block (#77) at 0x0014A808.
CRT detected that the application wrote to memory after end of heap buffer.


(Press Retry to debug the application)
Critical error detected c0000374
coinFliping.exe 已触发了一个断点。

程序“[9048] coinFliping.exe”已退出，返回值为 0 (0x0)。

内存溢出
2.数组复制备份时直接复制会造成循环崩溃，需要使用memcpy。

原文链接：https://blog.csdn.net/JeetLiu/article/details/103263260