(Java实现) 洛谷 P1691 有重复元素的排列问题

题目描述

设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]++;

			}

		}

	}

}

巴特西

(Java实现) 洛谷 P1691 有重复元素的排列问题

最新文章

热门文章