Integrated Application Platform › Forums › General › Heaps Algorithm
- This topic has 2 replies, 2 voices, and was last updated 6 years, 1 month ago by
ajith.
-
AuthorPosts
-
August 18, 2017 at 11:57 pm #1323
ajith
ParticipantHi,
I wanted to generate all possible pemutations for a given set. Internet search led me to Heaps algorithm. The suneido code I wrote based on http://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/ is given below
function(ob, size, result) { if (size == 1) { result.Add(ob.Copy()) return; } for ( i=0; i<size; i++) { HeapsPermutations(ob,size-1,result); // if size is odd, swap first and last element if (size%2==1) ob.Swap(0, size-1); // if size is even, swap ith and last element else ob.Swap(i, size-1); } return result }
As this is a recursive function, I need to supply the size of the original object and an empty object to store result when I call the function the first time. Other than creating a dummy function that would just accept the object which in turn would call the actual function (as given below), is there any other way to be able to call the actual function with just the object?
function(ob) { HeapsPermutations(ob,ob.Size(), Object()) }
Thanks,
ajithAugust 19, 2017 at 7:50 am #1324amckinlay
KeymasterHi Ajith,
That is often awkward with recursive functions. There are several options.
One is to have default values for the extra parameters. However, default values must be constants so you need to do something like:
function (ob, size = false, result = false) { if size is false size = ob.Size() if result is false result = Object()
This is the simplest, but the extra parameters could confuse users.
Another option is to use two functions but to bundle them together, either using a class:
class { CallClass(ob) { return .permute(ob, ob.Size(), Object()) } permute(ob, size, result) { ... // recursively calling .permute } }
CallClass is special so this can still be called like a function.
Or you can use a block:
function (ob) { permute = {|ob, size, result| ... // recursively calling permute result // without 'return' because that would return from outer function } return permute(ob, ob.Size(), Object()) }
August 22, 2017 at 9:41 pm #1327ajith
ParticipantHi Andrew,
Thanks for your reply. I am really amazed to see so much options. I have decided to go with the CallClass way. The zipped exported library record is attached. Please do include it in next release if you think it would be useful for others too.
Thanks,
ajithAttachments:
You must be logged in to view attached files. -
AuthorPosts
- You must be logged in to reply to this topic.