[Class] permutations.ahk

Post your working scripts, libraries and tools
User avatar
Chunjee
Posts: 707
Joined: 18 Apr 2014, 19:05
GitHub: Chunjee

[Class] permutations.ahk

29 Aug 2020, 13:29

permutations.ahk

Generates all possible permutations of the input array or string using Heap's algorithm, which minimizes movement.

Installation
In a terminal or command line navigated to your project folder:

Code: Select all

npm install permutations.ahk
In your code:

Code: Select all

#Include %A_ScriptDir%\node_modules
#Include permutations.ahk\export.ahk

result := permutations.generate("ahk")
; => [["a","h","k"], ["h","a","k"], ["k","a","h"], ["a","k","h"], ["h","k","a"], ["k","h","a"]]

result := permutations.generate("ahk", true)
; => ["ahk", "hak", "kah", "akh", "hka", "kha"]

result := permutations.generate(["Auto", "Hot", "key"], true)
; => ["AutoHotkey", "HotAutokey", "keyAutoHot", "AutokeyHot", "HotkeyAuto", "keyHotAuto"]

result := permutations.generate("AutoHotkey", true, 3)
; => ["AutoHotkey", "uAtoHotkey", "tAuoHotkey"]

You may also review or copy the package from ./export.ahk on GitHub; #Include it however you would normally when manually downloading a library.

API
Including the module provides a class `permutations` with one method: .generate

generate(array, [stringOut, maxPermutations])
Returns an array containing all possible permutations.

Arguments
  1. array (*): The array or string to find permutations of
  2. stringOut (bool): Optional, whether or not not elements of the return array should be combined into strings. Default is false meaning the result will be an array of arrays.
  3. maxPermutations (number): Optional, whether or not the number of permutations should be capped. This may be useful when dealing with a number of permutations that would otherwise take an excessive time to compute.
Returns
(array): An array containing all permutations.
Last edited by Chunjee on 12 Sep 2020, 12:41, edited 2 times in total.
User avatar
Chunjee
Posts: 707
Joined: 18 Apr 2014, 19:05
GitHub: Chunjee

Re: [Class] permutations.ahk

29 Aug 2020, 13:30

v0.1.2

Code: Select all

class permutations {
	; --- Static Methods ---
	generate(param_array, param_stringOut:=false, param_maxPermutations:="") {
		savedBatchLines := A_BatchLines
		SetBatchLines, -1

		; prepare inputs
		if (!IsObject(param_array)) {
			param_array := StrSplit(param_array)
		}

		; create
		this.outArray := []
		l_length := param_array.Count()
		l_permutationsArray := this._gen(l_length, param_array.Clone(), param_maxPermutations)

		; return array of arrays if user didn't specify param_stringOut
		if (param_stringOut == false) {
			SetBatchLines, % savedBatchLines
			return l_permutationsArray
		}
		l_outArrayStringified := []
		for _, l_obj in l_permutationsArray {
			l_string := ""
			for l_index, l_value in l_obj {
				l_string .= l_value
			}
			l_outArrayStringified.push(l_string)
		}
		SetBatchLines, % savedBatchLines
		return l_outArrayStringified
	}

	_gen(param_n:="", param_array:="", param_maxPermutations:="") {
		; prepare defaults
		if (param_n == "") {
			param_n := param_array.Count()
		}

		; create
		if (param_n == 1) {
			this.outArray.push(param_array.Clone())
		}
		loop, % param_n
		{
			; exit early if user specified param_maxPermutations and that number is reached
			if (param_maxPermutations) {
				if (param_maxPermutations <= this.outArray.Count()) {
					return this.outArray
				}
			}
			this._gen(param_n - 1, param_array, param_maxPermutations)
			if (mod(param_n, 2) != 0) {
				this._swap(param_array, 1, param_n) ;odd
			} else {
				this._swap(param_array, A_Index, param_n)
			}
		}
		return this.outArray
	}

	_swap(param_array, param_index1, param_index2) {
		tempVar := param_array[param_index1]
		param_array[param_index1] := param_array[param_index2]
		param_array[param_index2] := tempVar
		return param_array
	}
}
Last edited by Chunjee on 29 Aug 2020, 22:53, edited 2 times in total.
User avatar
Chunjee
Posts: 707
Joined: 18 Apr 2014, 19:05
GitHub: Chunjee

Re: [Class] permutations.ahk

29 Aug 2020, 13:31

I had some trouble with the 2019 AHK challenge for February. The challenge was to find any anagrams for a given word in another list. I discovered Heap's algorithm and even some ahk implementations on Rosetta code. However, I still had trouble because I wasn't able to solve some of the global scope infractions I felt those had. I think Heap's algorithm is somewhat difficult to achieve in a standalone function, but when I went-about it using a class, I didn't have much trouble at all. I hope anyone who needs this functionality will find this class useful; and portable enough to quickly apply in their project.

This class accepts both arrays and plain strings. It has two optional parameters that format the output for added convenience.


Ah yes, I was able to complete the challenge with the help of permutations.ahk: https://github.com/Chunjee/AHKChallenge2019-02
User avatar
Relayer
Posts: 138
Joined: 30 Sep 2013, 13:09
Location: Delaware, USA

Re: [Class] permutations.ahk

02 Sep 2020, 11:13

Chunjee,

Can this be altered to give all possible permutations taking a out of b where a < b and b is the length of the input?

Relayer
User avatar
Chunjee
Posts: 707
Joined: 18 Apr 2014, 19:05
GitHub: Chunjee

Re: [Class] permutations.ahk

02 Sep 2020, 15:07

I'm afraid I don't understand the question.

The source is open; so modification is absolutely possible, and encouraged.
ozzii
Posts: 375
Joined: 30 Oct 2013, 06:04

Re: [Class] permutations.ahk

03 Sep 2020, 05:14

In your example you have 'node_modules'
Where is this file (if needeed). I can't find it into your GitHub.
User avatar
Chunjee
Posts: 707
Joined: 18 Apr 2014, 19:05
GitHub: Chunjee

Re: [Class] permutations.ahk

03 Sep 2020, 10:15

Not sure how to better explain this in the readme but it needs to happen. "%A_ScriptDir%\node_modules" is just a directory packages are sent to when using the package manager. If you are manually downloading the library, you can put export.ahk anywhere AHK uses naturally ( https://www.autohotkey.com/docs/Functions.htm#lib ), or specify the exact location.

Return to “Scripts and Functions”

Who is online

Users browsing this forum: No registered users and 27 guests