精华内容
下载资源
问答
  • 有重复元素排列问题

    千次阅读 2017-04-10 15:51:07
    有重复元素排列问题问题描述】 设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法,列出R的所有不同排列。 【编程任务】 给定n 以及待排列的n 个元素。...

    有重复元素的排列问题
    【问题描述】
    设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法,列出R的所有不同排列。
    【编程任务】
    给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。
    【输入格式】
    文件的第1 行是元素个数n,1≤n≤500。接下来的1 行是待排列的n个元素。
    【输出格式】
    计算出的n个元素的所有不同排列输出。文件最后1行中的数是排列总数。
    【输入样例】
    4
    aacc
    【输出样例】多解
    aacc
    acac
    acca
    caac
    caca
    ccaa
    6
    解题思路:单从排列的所有可能数出发,可以直接使用
    这里写图片描述

    其中M为字符总数,ni表示其中重复字符数。但是考虑到需要把所有可能的排列结果输出,所以还需遍历所有可能的排序,
    最后统计所有可能排序的总数。假设,没有重复字符的情况,则是对应M个位置,每个位置所有可能字符数的乘积M!即为排列总数。
    现在有重复元素,同样借助无重复字符排序方式来求解。首先有重复字符串构成一个无重复字符的字符串,
    同时为新串用一个辅助数组表示每个字符出现的次数。即abbac,排列成无重复序列abc,辅助数组为221。然后采用回溯法,
    先建立一个字符长度的数组,该数组的每一个位置都从无重复序列中选择一个可能的字符,每次选出一个字符,
    则辅助数组与该字符对应减一,表示该字符可用数减一。直到最后一个字符,每次到最后一个字符的时候,
    计数器count++同时把此时数组中排序的字符串输出,即为可能的排序。
    然后回溯到上一个位置遍历上次递归选出的无重复串中的下一个字符递归直到最后一个字符后(这里递归下去后,也会回溯),
    又往上回溯一步。这里一开始对初始化的字符串重新排列的原因就是为了在回溯到上一步时,
    保证选出的下一个字符与上一次递归选取的字符不同。

    例如abbac abc 221
    递归到最后:aabbc
    第一次回溯:aabcb
    第二次回溯:aacbb
    第三次回溯:ababc abacb abbac abcab abcba …
    第四次回溯:baacb baabc …

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include <stdlib.h>
    #define num 5
    using namespace std;
    char a[1000];//用来存储当前位置所选取的字符
    int ans;//用于统计所有可能的序列总数
    /**
    回溯法实现-有重复字符排序问题:
    能排除相同字符重排序的根本是因为在调用回溯之前,所有字符按重复排列好,由于回溯上一步时,虽然当前字符被++,
    循环遍历也不会再考虑选择当前字符,而是会选择当前字符的下一个字符,直到回溯到第一个字符选择新的可能字符
    
    */
    void dfs(int dep,char *p,int *q)
    {
        int r;
        if (dep==num)//表示排序完所有字符
        {
            ans++;//记录方案总数
            for (r=0; r<num; ++r)
                printf("%c",a[r]);//输出当前排序在a数组中的字符串
            printf("\n");
            return;
        }
        for (r=0; p[r]!='#'; ++r)
            if (q[r]>0)//如果这个字母没有取完
            {
                a[dep]=p[r];//a依然是记录数组
                q[r]--;//计数器-1
                dfs(dep+1,p,q);
                q[r]++;//回溯一步
            }
    }
    /***
    对所有出现的字符进行统计出现的次数,按首次出现顺序存入p指针,出现次数存入q指针
    */
    int strtj(char *p,int *q)
    {
        int i,j,k;
        for(i=0; i<num; i++)
        {
            if(p[i]!='#')
            {
                q[i]=1;
                for(j=i+1; j<num; j++)
                {
                    if(p[i]==p[j])
                    {
                        p[j]='#';
                        q[j]=0;
                        q[i]++;
                    }
                }
            }
        }
        for(j=0,i=0; i<num; i++,j++)
        {
            if(p[j]=='#')
            {
                for(k=j; k<num; k++)
                {//然后回溯到上一个位置遍历另一种可能(指的是所有不同字符中剩下的可选字符),
                    p[k]=p[k+1];
                    q[k]=q[k+1];
                }
                j--;
            }
        }
        p[j]='#';
        q[j]=0;
        return 0;
    }
    int main()
    {
        char *p;
        int *q;
        int i=0,j=0,n=0,k=0;
        p=(char *)malloc(num*sizeof(char));
        q=(int *)malloc(num*sizeof(int));
        for(i=0; i<num&&p[i]!='\n'; i++)
            cin>>p[i];
        for(i=0; i<num; i++)
        {
            q[i]=0;
        }
        strtj(p,q);//统计每个字符出现的次数,并存入p q指针中
        dfs(0,p,q);//回溯构建所有可能的序列,输出所有可能的序列
        printf("%d",ans);//输出所有可能的总数
        return 0;
    }
    展开全文
  • (Java实现) 有重复元素排列问题

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

    有重复元素的排列问题
    【问题描述】
    设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法,列出R的所有不同排列。
    【编程任务】
    给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。
    【输入格式】
    文件的第1 行是元素个数n,1≤n≤500。接下来的1 行是待排列的n个元素。
    【输出格式】
    计算出的n个元素的所有不同排列输出。文件最后1行中的数是排列总数。
    【输入样例】
    4
    aacc
    【输出样例】多解
    aacc
    acac
    acca
    caac
    caca
    ccaa
    6
    解题思路:单从排列的所有可能数出发,可以直接使用

    在这里插入图片描述
    其中M为字符总数,ni表示其中重复字符数。但是考虑到需要把所有可能的排列结果输出,所以还需遍历所有可能的排序,
    最后统计所有可能排序的总数。假设,没有重复字符的情况,则是对应M个位置,每个位置所有可能字符数的乘积M!即为排列总数。
    现在有重复元素,同样借助无重复字符排序方式来求解。首先有重复字符串构成一个无重复字符的字符串,
    同时为新串用一个辅助数组表示每个字符出现的次数。即abbac,排列成无重复序列abc,辅助数组为221。然后采用回溯法,
    先建立一个字符长度的数组,该数组的每一个位置都从无重复序列中选择一个可能的字符,每次选出一个字符,
    则辅助数组与该字符对应减一,表示该字符可用数减一。直到最后一个字符,每次到最后一个字符的时候,
    计数器count++同时把此时数组中排序的字符串输出,即为可能的排序。
    然后回溯到上一个位置遍历上次递归选出的无重复串中的下一个字符递归直到最后一个字符后(这里递归下去后,也会回溯),
    又往上回溯一步。这里一开始对初始化的字符串重新排列的原因就是为了在回溯到上一步时,
    保证选出的下一个字符与上一次递归选取的字符不同。

    例如abbac abc 221
    递归到最后:aabbc
    第一次回溯:aabcb
    第二次回溯:aacbb
    第三次回溯:ababc abacb abbac abcab abcba …
    第四次回溯:baacb baabc …

    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Scanner;
    import java.util.Set;
    
    
    public class youchongfuyuansudepailiewenti {
    	static Set<String> set = new HashSet<String>();
    	public static int n;
    	public static char [] num1;
    	public static boolean [] bool;
    	public static void main(String[] args) {
    		Scanner sc =new Scanner(System.in);
    		 n = sc.nextInt();
    		String s = sc.next();
    		 num1 = s.toCharArray();
    		 char [] num = new char [num1.length];
    		bool = new boolean [num1.length];
    //		String [] num = new String [num1.length+1];
    //		for (int i = 1; i < num.length; i++) {
    //			num[i]=num1[i-1];
    //		}
    		f(0,num);
    		Iterator it = set.iterator();
    		while(it.hasNext()){
    			System.out.println(it.next());
    		}
    		System.out.println(set.size());
    	}
    	public static void f(int a,char [] num){
    		if(a==n){
    			String s = "";
    			for (int i = 0; i < num.length; i++) {
    				s= s+num[i];
    			}
    			set.add(s);
    			return;
    		}
    		for (int i = 0; i < num.length; i++) {
    			if(!bool[i]){
    				bool[i]=true;
    				num[a]=num1[i];
    				f(a+1,num);
    				bool[i]=false;
    				num[a]=0;
    			}
    		}
    	}
    
    }
    
    
    展开全文
  • 有重复元素排列问题

    千次阅读 2019-11-11 23:55:20
    题目:有重复元素排列问题前言题目要求问题描述:算法设计要求:数据输入:结果输出:分析源代码输入输出示例总结 前言 这是王晓东所著的《计算机算法设计与分析》(第四版)第二章算法实现题的第5道(P41) 题目...

    前言

    这是王晓东所著的《计算机算法设计与分析》(第四版)第二章算法实现题的第5道(P41)

    题目要求

    问题描述:

    设集合R={r1,r2,…,r n}是要进行排列的n个元素,其中r1,r2,…,r n可能相同。 试着设计一个算法,列出R的所有不同排列。

    算法设计要求:

    给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。

    数据输入:

    由文件input.txt提供输入数据,文件的第1行是元素个数n,1<=n<=500。接下来的1行是待排列的n个元素。

    结果输出:

    程序运行结束时,将计算输出n个元素的所有不同排列到文件output.txt。文件最后一行中的数是排列总数。

    分析

    这种有重复元素的排列问题可以使用递归来解决。
    拿aacc来举例子。
    aacc共计四个元素,我们可以将之划分为3个元素的排列。然后再划分为2个,最后只剩单个元素则不用再排列。
    举例:
    aacc——>aacc——>aacc
    很明显,cc也无需排列,则排acc,有acc、cac、cca三种
    依次递归即可。

    源代码

    with open("input5.txt", mode='r') as f1:
        list1 = f1.read().split()
        n = int(list1[0])
        a = list(list1[1])
        b = []
    
        def diversal(list, position, end):
            # 此方法使用递归对有序列表进行调换顺序,从而生成新的排列组合
            if position == end:  # 如果递归到只剩一个元素
                d = list[:]
                b.append(d)  # 将序列自身添加到排列集合中
            else:
                for index in range(position, end):  # 做调换
                    list[index], list[position] = list[position], list[index]
                    diversal(list, position + 1, end)   # 递归调用diversal(),使递归向下继续进行
                    list[index], list[position] = list[position], list[index]
    
        diversal(a, 0, n)
    
        s = []
        # 一个递推式,目的是将b这一排列集合去重。产生的集合s就是没有重复排列的集合了
        [s.append(i) for i in b if i not in s]
        s_len = len(s)
        with open("output5.txt", mode='w+') as f2:
            for i in range(s_len):
    
                # 最后做将列表转化为字符串的操作,以便符合题目所要求的的输出格式
                s[i] = ''.join([j for j in s[i]])
                print((str(s[i])), file=f2)
    
            print(s.__len__(), file=f2)
    
    

    输入输出示例

    input5.txt

    4
    aacc
    

    output.txt

    aacc
    acac
    acca
    caac
    caca
    ccaa
    6
    
    

    总结

    这类全排列问题算是递归算法里面经常出现的题目了,注意处理这类关系要找出递归式子或递归规律,然后找准递归终止条件,做好去重的操作,还是比较 容易做出来的。

    展开全文
  • (Java实现) 洛谷 P1691 有重复元素排列问题

    万次阅读 多人点赞 2019-06-03 08:42:48
    设R={r1,r2,……,rn}是要进行排列的n个元素。其中元素r1,r2,……,rn可能相同。使设计一个算法,列出R的所有不同排列。 给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。 输入输出格式 输入格式...

    题目描述
    设R={r1,r2,……,rn}是要进行排列的n个元素。其中元素r1,r2,……,rn可能相同。使设计一个算法,列出R的所有不同排列。

    给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。

    输入输出格式
    输入格式:
    第1行:元素个数n(1<=n<500)

    第2行:一行字符串,待排列的n个元素

    输出格式:
    计算出的n个元素的所有不同排列,最后一行是排列总数。

    输入输出样例
    输入样例#1:
    4
    aacc
    输出样例#1:
    aacc
    acac
    acca
    caac
    caca
    ccaa
    6

    说明
    输出按字典顺序排

    import java.util.Scanner;
    
    public class youchongfuyuansudepailiewenti {
    	public static int[] f;
    	public static int[] a;
    	public static char[] str;
    public static int count=0,n=0;
    	public static void main(String[] args)  {
    		Scanner sc = new Scanner(System.in);
    		 n = sc.nextInt();
    		 String s = sc.next();
    		sc.close();
    		f = new int[27];
    		a = new int[501];
    		str = s.toCharArray();
    		for (int i = 0; i < n; i++) {
    			f[str[i] - 96]++;
    		}
    		dfs(1);
    		System.out.println(count);
    	}
    	public static void dfs(int step){
    		if (step==n+1) {
    			count++;
    			for (int i = 1; i <= n; i++) {
    				System.out.print((char)(a[i]+96));
    			}
    			System.out.println();
    			return;
    		}
    		for (int i = 1; i <=26; i++) {
    			if(f[i]>0){
    				a[step]=i;
    				f[i]--;
    				dfs(step+1);
    				f[i]++;
    			}
    		}
    	}
    
    }
    
    
    展开全文
  • 2-8 有重复元素排列问题 问题描述 设R=r1,r2,…,rnR=r1,r2,…,rnR={ r_1, r_2 , …, r_n}是要进行排列的n个元素。其中元素r1,r2,…,rnr1,r2,…,rnr_1, r_2 , …, r_n可能相同。试设计一个算法,列出R的所有...
  • 有重复元素排列问题 万幸不是打印出每个排列,只知道dfs没有重复的元素全排列,这种待学习。 没有考虑到复杂度,只是自己觉得好写 主要就是用map存储元素,这样函数直接确定map中是否重合,不用每次都找是否...
  • 有重复元素排列问题 解题报告

    千次阅读 多人点赞 2015-08-13 08:31:15
    有重复元素排列问题问题描述】  设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法,列出R的所有不同排列。 【编程任务】  给定n 以及待排列的n 个元素。...
  • 8594 有重复元素排列问题 时间限制:1000MS 内存限制:1000K 描述 Input 第1行是元素个数n,1 Output 程序运行结束时,将计算出输n个元素的所有不同排列。最后1行中的数是排列总数。 Sample Input 4 aacc...
  • 分治法——有重复元素排列问题

    千次阅读 2020-01-13 10:51:53
    设R={r1,r2,……,rn}是要进行排列的n个元素。其中元素r1,r2,……,rn可能相同。使设计一个算法,列出R的所有不同排列。 给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。 输入输出格式 输入格式...
  • 重复元素排列问题

    千次阅读 2016-10-13 16:13:15
    问题描述: 设集合R={r1,r2,...,rn}是要进行排列的n个元素,其中r1,r2,...,rn可能相同。...求含重复元素排列问题,首先先求出不含重复元素的全排列。根据分治法,我们求n个元素的全排列,可以求出n-1

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 147,468
精华内容 58,987
关键字:

有重复元素的排列问题