Finding all the unique permutations of a string without generating duplicates

by

First convert the string to a set of unique characters and occurrence numbers e.g. BANANA -> (3, A),(1,B),(2,N). (This could be done by sorting the string and grouping letters). Then, for each letter in the set, prepend that letter to all permutations of the set with one less of that letter (note the recursion). Continuing the “BANANA” example, we have: permutations((3,A),(1,B),(2,N)) = A:(permutations((2,A),(1,B),(2,N)) ++ B:(permutations((3,A),(2,N)) ++ N:(permutations((3,A),(1,B),(1,N))

Here is a working implementation in Haskell:

circularPermutations::[a]->[[a]]
circularPermutations xs = helper [] xs []
                          where helper acc [] _ = acc
                                helper acc (x:xs) ys =
                                  helper (((x:xs) ++ ys):acc) xs (ys ++ [x])

nrPermutations::[(Int, a)]->[[a]]
nrPermutations x | length x == 1 = [take (fst (head x)) (repeat (snd (head x)))]
nrPermutations xs = concat (map helper (circularPermutations xs))
  where helper ((1,x):xs) = map ((:) x)(nrPermutations xs)
        helper ((n,x):xs) = map ((:) x)(nrPermutations ((n - 1, x):xs))

More Related Contents:

  1. Pattern Programmings
  2. Recursive and non-recursive traversal of three degree tree
  3. How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number [closed]
  4. how to show time performance for merge sort? [closed]
  5. Why this C code makes infinite loop?
  6. The most efficient way to implement an integer based power function pow(int, int)
  7. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  8. What integer hash function are good that accepts an integer hash key?
  9. How to reverse a singly linked list using only two pointers?
  10. Unique random number generation in an integer array [duplicate]
  11. Calculating factorial of large numbers in C
  12. Combine Gyroscope and Accelerometer Data
  13. Building a logarithm function in C without using float type
  14. Power by squaring for negative exponents
  15. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  16. C How to “draw” a Binary Tree to the console [closed]
  17. How to do unsigned saturating addition in C?
  18. Traverse Matrix in Diagonal strips
  19. Program to print permutations of given elements [closed]
  20. C – How to implement Set data structure?
  21. Calculating the Amount of Combinations
  22. Correctness of Sakamoto’s algorithm to find the day of week
  23. Rolling median in C – Turlach implementation
  24. Find maximum of three number in C without using conditional statement and ternary operator
  25. Algorithm to find all the exact divisors of a given integer
  26. Which is better way to calculate nCr
  27. Merging two sorted linked lists
  28. a working non-recursive floodfill algorithm written in C?
  29. Algorithm to pick values from array that sum closest to a target value?
  30. Avoid Overflow when Calculating π by Evaluating a Series Using 16-bit Arithmetic?

Leave a Comment