精华内容
下载资源
问答
  • 1. 不可重复全排列 全排列问题一般要求按照字典顺序排列出来. 例如: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 全排列问题一般尝试用递归的方式去做,用 for 循环来解决字典序的问题. #include <cstdio...

    全排列

    1. 不可重复全排列

    全排列问题一般要求按照字典顺序排列出来.

    例如:

    1 2 3     1 3 2

    2 1 3     2 3 1

    3 1 2     3 2 1

    全排列问题一般尝试用递归的方式去做,用 for 循环来解决字典序的问题.

    #include <cstdio>
    using namespace std;
    const int N=1024;
    int vis[N];
    int A[N];
    void print_permutation(int n,int cur)
    {
    	if (cur==n)			//cur==n 表示已经得到一组排列,输出 
    	{
    		for (int i=0;i<n;i++)
    			printf ("%d ",A[i]);
    		printf ("\n");
    		return ; 
    	}
    	for (int i=1;i<=n;i++)//for 循环中依次增大,保证了字典序
    	{
    		if (vis[i]==0)//当元素 i 没有出现,则加入当前 A 中 
    		{
    			A[cur++]=i;
    			vis[i]=1;
    			print_permutation(n,cur);
    			cur--;		//注意恢复变量,这样在下一层的排列中,元素 i 可以被选中 
    			vis[i]=0;
    		}
    	}
    }
    int main()
    {
    	int n;
    	scanf ("%d",&n);
    	print_permutation(n,0);
    	return 0;
    } 

    2. 可重复全排列

    之前的代码只能保证1-n的全排列,但是待排列元素不是1~n,比如是 1 1 2 的排列

    排列如下:

    1 1 2

    1 2 1

    2 1 1

    新的要求下,我们要对代码进行小小的改动。

    设置读入数组P[N],读入可重复元素序列,统计每个元素出现的次数;

    在递归的时候,我们只需要检查某元素在A数组中出现次数和P数组中次数是否相等即可。若不相等,可以继续添加,否则不能继续添加。

    除了这个之外,我们还应该考虑重复枚举的状况。

    例如:1 1 1 2

    在排列中多次枚举中重复出现

    1 1 1 2、1 1 1 2 或者 1 2 1 1 、 1 2 1 1 等其他情况。

    我们只需要保证同一层递归中,当前添加的元素和上一次添加的元素不同即可。

    代码如下:

    #include <cstdio>
    #include <algorithm> 
    using namespace std;
    const int N=1024;
    int A[N];
    int P[N]; 
    int vis_A[N],vis_P[N]; //这里注意数组范围应与实际元素范围匹配
    void print_permutation_repitition(int n,int cur)
    {
    	if (cur==n)
    	{
    		for (int i=0;i<n;i++)
    			printf ("%d ",A[i]);
    		printf ("\n");
    		return ; 
    	}
    	int last=-111; 
    	for (int i=1;i<=n;i++)
    	{
    		if (vis_P[P[i]]!=vis_A[P[i]]&&P[i]!=last)//判断出现次数是否相等 && 是否和前一个枚举的元素相等. 
    		{
    			last=P[i];
    			A[cur++]=P[i];
    			vis_A[P[i]]++;
    			print_permutation_repitition(n,cur);
    			cur--;
    			vis_A[P[i]]--;
    		}
    	}
    }
    int main()
    {
    	int n;
    	scanf ("%d",&n);
    	for (int i=1;i<=n;i++)
    	{
    		scanf ("%d",&P[i]);
    		vis_P[P[i]]++;	//统计次数 
    	}
        sort(P+1,P+n+1);//排序一下,保证字典序
    	print_permutation_repitition(n,0);
    	return 0;
    } 

     

    展开全文
  • /* 华科机试练手 * 回溯法解决 排列组合... * 3 : 不可重复的选择排序 * …… */ #include #include int solution[100]; /* 可重复全排 */ int Perm(int a[], int n, int level) { int i; static int sum = 0
    /* 华科机试练手
     * 回溯法解决 排列组合问题
     * 1 : 全排列
     * 2 :可重复全排列
     * 3 : 不可重复的选择排序
     * ……
     */
    #include <stdlib.h>
    #include <stdio.h>
    int solution[100];
    
    /* 可重复全排 */
    int Perm(int a[], int n, int level)
    {
        int i;
        static int sum = 0;
        if(level == n)
        {
            sum++;
            for(i=0; i<level; i++)
                printf("%d\t",solution[i]);
            printf("\n");
            return;
        }
        for(i=0; i<n; i++)
        {
            if(1)
            {
                solution[level] = a[i];
                Perm(a,n,level+1);
            }
        }
        return sum;
    }
    /* 不可重复全排 */
    int NoReptPerm(int a[], int n, int level)
    {
        int i,j,selected = 0;
        static int sum = 0;
        if(level == n)
        {
            sum++;
            for(i=0; i<level; i++)
                printf("%d\t",solution[i]);
            printf("\n");
            return;
        }
        for(i=0; i<n; i++)
        {
            selected = 0;
            for(j=0; j<level; j++)//检查是否已经被选过
            {
                if(solution[j] == a[i])
                {
                    selected = 1;
                    break;
                }
            }
            if(!selected)//没被选过
            {
                solution[level] = a[i];//加入解向量
                NoReptPerm(a,n,level+1);
            }
        }
        return sum;
    }
    /* 选择排序(不可重复) */
    int SelectPerm(int a[], int n, int m, int level)
    {
        int i,j,selected = 0;
        static int sum = 0;
        if(level == m)
        {
            sum++;
            for(i=0; i<level; i++)
                printf("%d\t",solution[i]);
            printf("\n");
            return;
        }
        for(i=0; i<n; i++)
        {
            selected = 0;
            for(j=0; j<level; j++)//检查是否已经被选过
            {
                if(solution[j] == a[i])
                {
                    selected = 1;
                    break;
                }
            }
            if(!selected)//没被选过
            {
                solution[level] = a[i];//加入解向量
                SelectPerm(a,n,m,level+1);
            }
        }
        return sum;
    }
    int main(int argc, char *argv[])
    {
        int i;
        int a[] = {1,2,3};
        i = Perm(a,3,0);
        printf("Total : %d\n",i);
        i = NoReptPerm(a,3,0);
        printf("Total : %d\n",i);
        i = SelectPerm(a,3,2,0);
        printf("Total : %d\n",i);
        return 1;
    }
    

    展开全文
  • #若想遍历一个集合中元素的所有可能的排列或组合 #itertools模块提供了三个函数来解决这类问题。其中一个是itertools.permutations(),它接受一个集合并产生 #一个元组序列,每个元组由集合中所有元素的一个可能排列...
    #若想遍历一个集合中元素的所有可能的排列或组合
    #itertools模块提供了三个函数来解决这类问题。其中一个是itertools.permutations(),它接受一个集合并产生
    #一个元组序列,每个元组由集合中所有元素的一个可能排列组成,也就是说通过打乱集合中元素排列顺序生成一个元组
    items=['a','b','c']
    from itertools import permutations
    for p in permutations(items):
        print(p)

    #若想得到指定长度的所有排列,你可以传递一个可选的长度参数
    for p in permutations(items,2):
        print(p)

    #使用itertools import combinations()可得到输入集合中元素的所有的组合
    from itertools import combinations
    for c in combinations(items,3):  #3个元素的组合
        print(c)
    for c in combinations(items,2):
        print(c) 
    for c in combinations(items,1):  #1个元素的组合
        print(c)

    #对combinations()来讲,元素顺序已经不重要了,就是说组合('a','b')跟('b','a')一样(最终只会输出其中一个)
    #在计算组合时,若元素已被选取就会从候选中剔除(若a已被选,接下来不会再考虑它)
    #itertools.combinations_with_replacement()允许同一个元素被选择多次。
    from itertools import combinations_with_replacement
    for c in combinations_with_replacement(items,3):
        print(c)

    展开全文
  • // 12个字母任选5个进行排列组合,不可重复 var array = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']; var len = array.length; var result = []; // for (var i = 0; i // for (var j = i...
    // 12个字母任选5个进行排列组合,不可重复
    
    var array = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'];
    var len = array.length;
    var result = [];
    // for (var i = 0; i < len; i++) {
    // for (var j = i+1; j < len; j++) {
    // for (var k = j+1; k < len; k++) {
    // for (var m = k+1; m < len; m++) {
    // for (var n = m+1; n < len; n++) {
    // var tm = [array[i],array[j],array[k],array[m],array[n]];
    // result.push(tm);
    // }
    // }
    // }
    // }
    // }
    // console.log(result);


    var indexs = {};
    function recursionSub(ind, start) {
        start++;
        if (start > 4) {
            return;
        }
        if (!indexs[start]) {
            indexs[start] = 0;
        }
        for (indexs[start] = ind; indexs[start] < len; indexs[start]++) {
            recursionSub(indexs[start] + 1, start);
            if (start == 4) {
                var temp = [];
                for (var i = 4; i >= 0; i--) {
                    temp.push(array[indexs[start - i]]);
                }
                result.push(temp);
            }
        }
    }
    recursionSub(0, -1);
    console.log(result);
    展开全文
  • 可重复全排列与不可重复全排列

    千次阅读 2020-05-14 11:54:22
    可重复全排列即在排列中会有重复元素。下面是全排列的递归写法: 假设我们有数组a[5]={3, 4, 5, 6, 7},且我们想知道这个数组的全部排列。 我们可以从第零位开始与后面所有位进行交换,交换完递归下一层,下一层从第...
  • 1. 使用标记法求解#include #include using namespace std; int vis[100]; //标记数组,直接判断需要循环判断,循环见全排列2.cpp int re[]= {2,1,2};...void dfs(int cur,int border)//可以去除重复排列
  • 问题描述: 键盘输入一个仅由小写字母组成的字符串,输出以该串中任 取M个字母的所有排列排列总数。 例如:输入字符串abcd,输入m=3 则输出为:abc,abd,acd,bcd,n=4
  • 排列组合(可重复版)

    千次阅读 2018-11-08 13:38:20
    =P[i-1]) {//下标不重复 int ok = 1; int c1 = 0, c2 = 0; for (int j = 0; j ; j++) if (A[j] == P[i])c1++;//计算P[i]在数组A中出现了多少次 for (int j = 0; j ; j++)if (P[i] == P[j])c2++;//计算P[i]在...
  • <?php /** * 无重复排列組合 * @Author MAX * @DateTime 2018-09-07T16:28:40+0800 * @param Array $arr 需要排列組合的数组 * @param Number $m 每几个一組 * @param...
  • (Java实现) 有重复元素排列问题

    万次阅读 多人点赞 2019-06-02 08:31:41
    重复元素的排列问题 【问题描述】 设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法,列出R的所有不同排列。 【编程任务】 给定n 以及待排列的n 个元素。计算...
  • 求全排列(可重复)next_permutation

    千次阅读 2012-10-21 11:09:01
    字典序列算法   字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。...它的整体思想是让排列成为递推的数列,也就是说从前一状态的排列,可以推出一种新的状态,直到最终
  • 输出4个整数(不重复)的所有排列组合

    万次阅读 多人点赞 2017-03-30 22:10:41
    这是一个经典问题,具体问题:从1-13的整数里,选择四个数字,允许重复,并运用+,-,*,/,()对这四个数字进行运算,如果答案等于24,则输出“yes”,否则输出“no”。 最开始以为能找到规律,但是想了很久,...
  • 组合排列重复数问题

    千次阅读 2019-08-27 14:30:59
    但是当出现重复数字时就不好处理了,比如[1,2,1,4],在回溯的过程中,会出现相同的排列,使用两个相同的1造成的,程序的逻辑本身没有错。其实全排列就是递归树,如下所示 观察发现,第二个子树刚开始能能选1呢...
  • 重复元素的排列问题

    千次阅读 2019-03-08 08:16:01
    1.问题描述 ... 即,给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。 2.算法设计 给定n及待排列的n个元素,计算出这n个元素的所有不同排列。 3.数据输入 第1行是元素个数n,1&l...
  • java从文本中读取单词,并将所有不重复单词按升序排列下载
  • 那么P(A[i],..,P[j])会产生重复排列。 改进的实现如下: void GenePermu(int A[], int i, int n) { if (i == n-1) { for (int k = 0; k ; ++k) { cout[k]; } cout; return; } else { ...
  • JAVA集合中不可重复性与是否有顺序

    千次阅读 2015-06-21 09:50:35
    List 中 ...如图:可见存储空间是有顺序的,当然放重复数据时候也可以清晰分别。所以可以重复。可见存储空间是有顺序的,当然放重复数据时候也可以清晰分别。所以可以重复。     Linkl...
  • 如题: 位置自由挑换,但是重复如:12345,12346,12347,12348,12349这样。 java算法,提供思路也行。
  • 求一个序列的全排列,字典序,序列中的元素无重复,在实际应用过程中,可以按下标来做计算
  • 如:1 2 3 4 取3个 则有1 2 3,1 2 4,1 3 4,2 3 4 public class mAn {  public static String str = "";  public static char a[];    public static void f(int n,int m){ ... S...
  • 编号为1~n s (例如,有3个a,两个b,先排列成aabba,然后可以编号为a 1 a 3 b 2 b 1 a 2 )。这样 做以后,由于编号后所有元素均相同,方案总数为n的全排列数n!。根据乘法原理,得到 了一个方程:n 1 !n 2 !...
  • 注意百位能为0; 编译环境:vc++6.0 #include <stdio.h> /*穷举*/ int main() { int x; for (int i = 1; i <= 4; i++) for (int j = 0; j <= 4; j++) { for (int k = 0; k <= 4; k++) ...
  • 题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由...输入一个字符串,长度超过9(可能有字符重复),字符只包括大小写字母。 void Per(int begin,string &str,vect
  • 数组 $array = [1,2,3,4]; // 多位数也可以 以下是所需的结果 以下是具体实现代码 public function getSortCartList($array,$level = -1,&amp;amp;$list =[]) { for ($i=0; $i &... ...
  • 给定一个字符串,要求给出重新排列的所有相同的排列数 题目描述 给定一个只包含大写英文...再统计重复出现的字母,除去每个字母的排列次数 例如 对于ABA,当成三个不同字符则排列数为:S总=A33S_总=A_3^3S总​=A3...
  • Android瀑布流照片墙实现,体验规则排列的美感

    万次阅读 多人点赞 2013-09-06 08:35:18
    这个时候瀑布流布局的出现,就给人带来了耳目一新的感觉,这种布局虽然看上去貌似毫无规律,但是却有一种说上来的美感,以至于涌现出了大批的网站和应用纷纷使用这种新颖的布局来设计界面。 记得我在之前已经写过...
  • 计数的方法:重组合和全排列

    千次阅读 2018-10-23 21:01:53
    排列排列就是围成一个圆。圆旋转一下是同一个排列。因此 从n个中取r个的圆排列排列数为 P(n,r)/r ...这是因为r个中间有r个空隙,沿着r个空隙剪开可以分别得到r中排列。...项链排列 ...重...
  • List是有序且重复的,Set是无序不重复的。这里说的顺序有两个概念,一是按添加的顺序排列,二是按自然顺序a-z排列。Set并不是无序的,传统说的Set...不保证元素添加的顺序,不保证元素自然的顺序,不可重复:HashSet...
  • 生成重集的排列

    千次阅读 2015-06-04 21:38:40
    #include ...void printPermutation(int n, int* p, int cur, int* arr) //n是元素个数,p是初始元素集合,cur是当前位置,arr是目前已经排列的部分 { int i, j; if (cur == n) { for (i = 0; i ; i+

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 192,065
精华内容 76,826
关键字:

不可重复排列