10/7/2023 0 Comments Number of permutationsSTRING PERMUTATOR (after Filip Nguyen) InsertRepeats(combi, repeats.slice(0, pos) + repeats.slice(pos + 1)) Var total = 0, firsts = "", repeats = "" In my opinion, this is just one permutation and its double, and the correct answer is 1800 the algorithm below will return both results. However, this way of counting considers abcdefa and abcdefa to be two distinct permutations, "because the a's are swapped". I've seen this question with one repeated character, where the number of permutations of abcdefa where the two a's are kept seperate is given as 3600. Then recurse for each result with the remaining repeated characters.when inserting b into dbac, results are dbabc and dbacb Put the repeat two places or more after the first occuranceĮ.g.when inserting abc into dbac, use b first Start with the repeated character whose original comes first in the firstsĮ.g.Then, one by one, insert the repeats into each permutation, following these rules: Seperate the first occurances from the repeats: To find all permutations of a string with one or multiple repeated characters, while keeping identical characters seperated: It seemed like a straightforward enough problem, but I spent hours on the wrong track before finally figuring out the correct logic. So now we have to fill 5 boxes: one with 'aa', other with 'ff', and 3 with the remaining 'b', 'd' and 'e'.Īlso, each of those 'aa' and 'bb' can be permuted in 2! ways. We have to notice that some of the permutations with two 'a' together, will also have two 'f' together, and vice versa, so we need to add those back.Īs we have two repeated characters, we will consider two "compound" boxes: one for occurrences of 'aa' and other for 'ff' (both at the same time). If we had only one character repeated, the problem is finished, and the final result would be TOTAL - INVALID permutations.īut, if we have more than one repeated character, we have counted some of the invalid strings twice or more times. Of course, as we also have two 'f', the number of permutations with 'ff' will be the same as the ones with 'aa': So, the total number of permutations with two 'a' together is: We also have to consider that the two 'a' can be themselves permuted in 2! (as we have two 'a') ways. Now we have only six boxes, as one of them will be filled with 'aa': Our example string has two repeated characters: the 'a' appears twice, and the 'f' also appears twice. As they have to be together, why don't consider them something like a "compound" character? To calculate them, we'll consider that any character that has the same character side by side, will be in the same box. So the total number of permutations, without restrictions, is:Īny permutation with two equal characters side by side is not valid. We can fill the first with any of the 7 characters, the second with any of the remaining 6, and so on. Which has 7 characters, there are seven boxes to fill. Let's consider each position a small box. We have to fill a number of positions, that is equal to the length of the original string. To find the solution we have to calculate the total number of permutations (without restrictions), and then subtract the invalid ones. This is a mathematical approach, that doesn't need to check all the possible strings. ![]() The maths to resolve the case where only one character is repeated is pretty trivial - Factorial of total number of characters minus number of spaces available multiplied by repeated characters.īut trying to figure out the formula for the instances where more than one character is repeated has eluded me. I posted this question on math.stackexchange. But I really want to try to resolve this problem efficiently rather than brute force through an array of all possible permutations. I have read through a lot of post about Combinatorics and Permutations and just seem to be digging a deeper hole for myself. The tests for this problem are as follows (returning the number of permutations that meet the criteria)- "aab" should return 2 The problem sees each character as unique so maybe "aab" could better be described as "a1a2b" The example given in the problem is "aab" which the site says has six possible permutations, with only two meeting the non-repeated character criteria: Second question - If yes, what formula could I use? I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.īut I have this gnawing feeling that I can solve this mathematically. Have the same letter (in this case 'a') repeating. Return 2 because it has 6 total permutations, but only 2 of them don't Return the number of total permutations of the provided string thatĭon't have repeated consecutive letters. I'm working on a Free Code Camp problem.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |