Heaps Algorithm

[ajithParticipant]

Hi,

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,
ajith

[amckinlayKeymaster]

Hi 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())
    }

[ajithParticipant]

Hi 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,
ajith

Attachments:

You must be logged in to view attached files.

[Author]

Posts