memory limit reached during permutation

[BGM]

Hi, all.
I published a little program called Ballistic in DC's NANY.

One the users there decided to test the permutation function with seventeen letters and it gives up an error.
Here I have run the uncompiled script for the sake of debugging.
Also the function is included below.

Code: Select all

;http://www.autohotkey.com/board/topic/32472-anagram-bot/#entry206401    function by [VxE]
;returns a newline-seperated list of all unique permutations of the input set.
 ; Note that the length of the list will be (N!)
twister_Permutate(set,delimeter="",trim="", presc=""){
	d := SubStr(delimeter,1,1)
	StringSplit, m, set, %d%, %trim%
	IfEqual, m0, 1, return m1 d presc
	Loop %m0%
	{
		remains := m1
		Loop % m0-2
			x := A_Index + 1, remains .= d m%x%
		list .= twister_Permutate(remains, d, trim, m%m0% d presc)"`n"
		mx := m1
		Loop % m0-1
			x := A_Index + 1, m%A_Index% := m%x%
		m%m0% := mx
	}
	return substr(list, 1, -1)
}

I've tried setting #maxmem to 500 but I still get the error.
Any clues?

[kon]

; Note that the length of the list will be (N!)

Even with #MaxMem 4095 the length of the string returned by the funciton quickly exceeds memory capacity. The large number of permutations will limit doing much more than n=11.

Code: Select all

StrLen(Word)	StrLen(twister_Permutate(Word))
1				1
2				5
3				23
4				119
5				719
6				5039
7				40319
8				362879
9				3628799
10				39916799
11				479001599

[BGM]

Is there another way? Or for my program, should I just place a limit on character input to prevent the error?

[kon]

For longer words you may be better off comparing the word to a dictionary instead of calculating all n! permutations.

[jNizM]

Here is an old script by IsNull (wGEN.ahk)
It works, but he never finished it. Maybe it helps you with your permutations.

[BGM]

jNizM - thanks for that! That does do permutations like mine does, but with some extras.
That script estimates the size of the list, too.
But mine is much faster, I have to admit, but this one doesn't seem to suffer from the memory problem.

But maybe I can learn something! Thanks a lot!

[strobo]

The "memory problem" is a consequence of 17! > 3.5e+14, which in turn is the main problem. Even at a GHz production rate, creating all those strings would take more than 4 days (btw the ahk code is probably 1000 times slower, i.e. > 10 years).

[BGM]

What I'd like to do is to allow for the function to go ahead and run for four days. I know it will take a long time. However, IsNull's script seems to not suffer, so as soon as get time I'm giong to adapt to it.