计算没有两个相邻字符相同的所有排列

本文介绍了计算没有两个相邻字符相同的所有排列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定一个仅包含数量不同的数字1、2、3和4的序列(例如:13244、4442等)，我想计算其所有排列，以使没有两个相邻的数字相同.我相信它是O(N！* N)，想知道那里是否有更好的一个.有人有什么想法吗?

Given a sequence which contains only various amounts of the numbers 1, 2, 3, and 4 (examples: 13244, 4442, etc), I want to count all its permutations such that no two adjacent numbers are the same. I believe it is O(N! * N) and want to know if there is a better one out there. Anyone have any ideas?

class Ideone { static int permutationCount++; public static void main(String[] args) { String str = "442213"; permutation("", str); System.out.println(permutationCount); } private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0){ boolean bad = false; //Check whether there are repeating adjacent characters for(int i = 0; i < prefix.length()-1; i++){ if(prefix.charAt(i)==prefix.charAt(i+1)) bad = true; } if(!bad){ permutationCount++; } } else { //Recurse through permutations for (int i = 0; i < n; i++) permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); } } }

推荐答案

我理解您的问题，例如:给出一个仅包含数字1,2,3,4的字符串-这些字符存在多少种排列，当您再将它们放入字符串中，就不会有相同的相邻数字.

I understand your question like this: Given a string containing only numbers 1,2,3,4 - how many permutations of these characters exist that when you put them into string again there won't be any same adjecent numbers.

我建议采用这种方法:

L - length of your string n1 - how many times is 1 repeated, n2 - how many times is 2 repeated etc. P - number of all possible permutations P = L! / (n1!*n2!*n3!*n4!) C - number of all solutions fitting your constraint C = P - start with all permutations substract all permutations which have 11 in it (just take 11 as one number) C = C - (L - 1)! / ((n1 - 1)! * n2! * n3! * n4!) ... do the same for 22 ... add all permutations which have both 11 and 22 in it (because we have substracted them twice, so you need to add them) C = C + (L - 2)! / ((n1 - 1)! * (n2 - 1)! * n3! * n4!) ... repeat previous steps for 33 and 44 ...