C语言怎么实现有重复元素的排列公式全排列？

来源：蜘蛛抓取(WebSpider) 时间：2022-11-03 12:35 标签： 有重复元素的排列公式

问题描述：设R={ r1, r2, ..., rn}是要进行排列的n个元素。其中元素r1, r2, ...,rn可能相同。试设计一个算法，计算出这n个元素的所有不同排列数。Input每组测试数据首先是n(1<=n<=500)，接着是待排列的n个元素(小写字母)。Output输出排列总数。Sample Input

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯的某个的点称为“回溯点”。 ——百度百科

全排列回溯的基本思想：对当前位置依次进行与后面所有位置的一个交换，然后对交换后的当前位置之后的元素进行一个全排列，全排列完毕后，进行回溯：将当前位置与之前交换的位置重新调换，形成原来的排列，然后继续进行下一次交换。

比如我们想要对[1, 2, 3, 4, 5]进行排列，首先确定第一位数，可以是1， 2， 3 ， 4 ，5中任意一个，下图中我们与3进行交换，那么交换后的后四个数就是[2, 1, 4, 5]，然后对这个数组进行全排列(递归)，最后回溯之后就会回到[1, 2, 3, 4, 5]（每次排列都会回溯，所以最外层回溯的时候的排列和起初一定是一样的），接下来把4作为首位，需要排列的数就是[2, 3, 1, 5]，依次类推。

我要回帖

更多关于 有重复元素的排列公式 的文章

 

随机推荐