20928

Non-recursive algorithm for full permutation with repetitive elements?

I usually use the recursive algorithm as follows in Python:

def permutate(array, t, n): if t == n: for i in range(n): print array[i] return for j in range(t,n): flag = 1 for r in range(t,j): if array[r] == array[j]: flag = 0 break if flag == 0: continue else: array[j],array[t] = array[t],array[j] permutate(array,t+1,n) array[j],array[t] = array[t],array[j]

This one is neat. But I hope to find a convenient, non-recursive algorithm to do full permutation with repetitive elements?

Answer1:

Here is a generic way to "un-recursify" a recursive function : Let's say we have the following recursive function :

RecFunc (parameters) ... ... var x = RecFunc (other parameters) ... ... EndFunc

To "un-recursify" it, you can use a stack like this :

NonRecFunc (parameters) stack MyStack; MyStack.push (InitialValue); While (MyStack is non empty) var S = MyStack.pop; # begin operations with S .... # results are x_1, ..., x_n for x_i = x_1 to x_n MyStack.push (x_i); endfor endWhile EndFunc

In your case, the stack contains a pair consisting of an array and an int. The initial value is the array in input and the int m=0. The operations could look like this

for i = m to n for j = i+1 to n if array[i] == array[j] continue endif array_c = copy of array permute entries i and j in array_c push (array_c, m+1) in the stack endfor endfor

Good luck !

Recommend

  • “Call stack size exceeded” when porting Ruby code to JavaScript
  • Derive every possible combination of elements in array
  • How to get the remainder of a dataset
  • Permutations list repeating itself when returning ArrayList in toString method
  • Is there a simpler way to process check boxes?
  • Removing multiple recurring text from pandas rows`
  • Selecting an integer from each of the given n sets of integers such that the sum of their pairwise d
  • How to use fmt.Sscan to parse integers into an array?
  • is it possible to have partial xaml like partial class?
  • Add an entry to the legend for a manually added line
  • How can I cons a list of pairs on to auto-mode-alist?
  • C++ alternatives to preprocessor macro code generation?
  • Set text in TextView in custom dialog
  • Trying to string.Join an IList
  • Remove final comma from string in vb.net
  • print() is showing quotation marks in results
  • Make VS2015 use angular-cli ng at build time in a .NET project
  • Android fill_parent issue
  • How to do unit test for HttpContext.Current.Server.MapPath
  • Sails.js/waterline: Executing waterline queries in toJSON function of a model?
  • NetLogo BehaviorSpace - Measure runs using reporters
  • Spring security and special characters
  • Why HTML5 Canvas with a larger size stretch a drawn line?
  • Get object from AWS S3 as a stream
  • Why doesn't :active or :focus work on text links in webkit? (safari & chrome)
  • Submit form in a displaytag pagination
  • JSON with duplicate key names losing information when parsed
  • Can I have the cursor start on a particular column by default in jqgrid's edit mode?
  • Can a Chrome extension content script make an jQuery AJAX request for an html file that is itself a
  • When should I choose bucket sort over other sorting algorithms?
  • Unanticipated behavior
  • How to delete a row from a dynamic generate table using jquery?
  • C# - Getting references of reference
  • using HTMLImports.whenReady not working in chrome
  • Authorize attributes not working in MVC 4
  • How can I remove ASP.NET Designer.cs files?
  • python draw pie shapes with colour filled
  • EntityFramework adding new object to nested object collection
  • Is there any way to bind data to data.frame by some index?
  • How can i traverse a binary tree from right to left in java?