memory limit reached during permutation

Get help with using AutoHotkey and its commands and hotkeys
User avatar
BGM
Posts: 495
Joined: 20 Nov 2013, 20:56
GitHub: bgmCoder
Contact:

memory limit reached during permutation

16 Feb 2015, 10:35

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?
Attachments
screenshot_AutoHotkey (AutoHotkey Unicode 32-bit)_002.png
maxmem error
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

Re: memory limit reached during permutation

16 Feb 2015, 18:34

[VxE] wrote: ; 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
User avatar
BGM
Posts: 495
Joined: 20 Nov 2013, 20:56
GitHub: bgmCoder
Contact:

Re: memory limit reached during permutation

16 Feb 2015, 18:37

Is there another way? Or for my program, should I just place a limit on character input to prevent the error?
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

Re: memory limit reached during permutation

16 Feb 2015, 18:52

For longer words you may be better off comparing the word to a dictionary instead of calculating all n! permutations.
User avatar
jNizM
Posts: 2663
Joined: 30 Sep 2013, 01:33
GitHub: jNizM
Contact:

Re: memory limit reached during permutation

17 Feb 2015, 01:51

Here is an old script by IsNull (wGEN.ahk)
It works, but he never finished it. Maybe it helps you with your permutations.
[AHK] 1.1.32.00 x64 Unicode | [WIN] 10 Pro (Version 2004) x64 | [GitHub] Profile
Donations are appreciated if I could help you
User avatar
BGM
Posts: 495
Joined: 20 Nov 2013, 20:56
GitHub: bgmCoder
Contact:

Re: memory limit reached during permutation

17 Feb 2015, 12:09

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
Posts: 125
Joined: 30 Sep 2013, 15:24

Re: memory limit reached during permutation

23 Feb 2015, 09:38

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).
User avatar
BGM
Posts: 495
Joined: 20 Nov 2013, 20:56
GitHub: bgmCoder
Contact:

Re: memory limit reached during permutation

23 Feb 2015, 11:21

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.

Return to “Ask For Help”

Who is online

Users browsing this forum: Bing [Bot], draj, ra8ul and 27 guests