Jump to content
Sign in to follow this  
caleb41610

[SOLVED] Factorial & get all possible variations?

Recommended Posts

caleb41610

Well, this is what I have so far. I've searched a bit but haven't really found much. I'll post this here to see if anyone can offer input while I keep trying to figure this out myself.

$file = @ScriptDir & "\" & "factorial.txt"
$fileopen = FileOpen( $file, 1 )
$test = "abcd"

; part 1
MsgBox( 0, "Factorial", _Calculate_Factorial( $test ) )

;part 2
_Calculate_Results( $test )


Func _Calculate_Factorial( $string )
Local $length = StringLen( $string )
Local $result = $length
For $i = 1 To $length - 1
$result = $result * ( $length - $i )
Next
Return $result
EndFunc

Func _Calculate_Results( $string )
Local $result
Local $string_length = _Calculate_Factorial( $string )
For $i = 1 To $string_length
; ??
FileWrite( $file, $i & ": " & $result & @CRLF )
Next
EndFunc

example:

_Calculate_Results( "abc" ) needs to return..

1) abc

2) acb

3) bca

4) bac

5) cba

6) cab

in the text file

Edited by caleb41610

Share this post


Link to post
Share on other sites
UEZ

What are you trying to achieve? Do you want to calculate the factorial of an integer? Or do you want to create a file with each value of the calculation? Or both?

Br,

UEZ


Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share this post


Link to post
Share on other sites
Melba23

caleb41610,

Perhaps this might help: ;)

#include <Array.au3>

$sString = "abcd"
$aArray = StringSplit($sString, "", 2)
$aNewArray = _ArrayPermute($aArray, "")
_ArrayDisplay($aNewArray, "Array Permuted")

M23


Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______Open Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites
caleb41610

What are you trying to achieve? Do you want to calculate the factorial of an integer? Or do you want to create a file with each value of the calculation? Or both?

Br,

UEZ

Both. The first function works and gets the factorial. I'm stuck on the second part, making a list of each one.

Share this post


Link to post
Share on other sites
jchd

A factorial isn't what you think it is. The factorial of a strictly positive integer N is the product of all non-null integers up to N.

It's standard notation is:

N! = 1 * 2 * ... * (N-1) * N

What you were after is, as Melba23 showed, a list of all permutations of an ordered set, being modeled as strings of characters.

Note that the number of such permutations rapidly explodes as the size of the set grows.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
Melba23

jchd,

Knowing your expertise I hesitate to take you on when discussing such matters, but I think that technically it is a "factorial" - or so my maths textbook tells me:

The number of permutations of n distinct objects is n×(n − 1)×(n − 2)×⋯×2×1, which number is called "n factorial" and written "n!"

And I thought only the English went in for understatement. ;)

rapidly explodes

"Rapidly" is far too timid a description of what happens as you increase the number of elements. It is like describing a parsec as "a fair distance"! :D

M23


Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______Open Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites
jchd

Speaking of the number of such permutations, yes, it's obviously N! for a set of N elements.

But the enumeration of all these permutations isn't a factorial per se.

N! growth may seem very fast indeed, compared to the limited range of integers that typical programming languages usually manipulate, e.g. 264 or so. Even using AutoIt we can expand that range somewhat by using a large integer arithmetic UDF at the expense of much slower runtimes.

But in the idealistic world of math, N! is very ... unimpressive. People interested can read why here, for example.

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
Spiff59

My question would be...

If your input is "ABA" would you still want 6 permutations?

Or only 3?

Share this post


Link to post
Share on other sites
caleb41610

My question would be...

If your input is "ABA" would you still want 6 permutations?

Or only 3?

That somewhat shows what I'm eventually going to do in reverse. I'm going to get the permutation of a string, and stop at number X depending on an algorithm based on another string.

In the end, if X was 2, then ABC would be ACB (the second possible permutation) and so on.

The goal is my own hash-like output with a password. It's not intended to work backwards, though, so it's not encryption. I'm really not sure what else I want to do.

Share this post


Link to post
Share on other sites
Spiff59

If you wanted a permutation count that dropped "duplicates", these are expanded versions of something from a prior thread (I "UDF'ed" them and added some parameters):

Local $sInput = "abbbcdddda"
$s1 = _StringPermutationCount($sInput) ; dupes
$s2 = _StringPermutationCount($sInput, 1) ; no dupes
Local $aInput = Stringsplit($sInput, "")
$s3 = _ArrayPermutationCount($aInput) ; base 1, dupes
$s4 = _ArrayPermutationCount($aInput, 1, 1) ; base 1, no dupes
Local $aInput = Stringsplit($sInput, "", 1)
$s5 = _ArrayPermutationCount($aInput, 0) ; base 0, dupes
$s6 = _ArrayPermutationCount($aInput, 0, 1) ; base 0, no dupes
MsgBox(0,"", "String:" & @LF & $s1 & @LF & $s2 & @LF & @LF & "1-based array:" & @LF & $s3 & @LF & $s4 & @LF & @LF & "0-based array:" & @LF & $s5 & @LF & $s6 & @LF)
Exit

;===================================================================================================================================
Func _StringPermutationCount($sStr, $iNoDupes = 0)
    Local $aArray = StringSplit($sStr, ""), $iPerms = 1, $iDivisor
    For $i = 2 To $aArray[0] ; count permutations
        $iPerms *= $i
    Next
    If $iNoDupes Then
        For $x = 1 to $aArray[0] ; reduce count for each dupe
            If Not $aArray[$x] Then ContinueLoop
            $iDivisor = 2
            For $y = $x + 1 to $aArray[0]
                If $aArray[$y] = $aArray[$x] Then
                    $iPerms /= $iDivisor
                    $aArray[$y] = ""
                 $iDivisor += 1
                EndIf
            Next
        Next
    EndIf
    Return $iPerms
EndFunc

Func _ArrayPermutationCount($aArray, $iBase = 1, $iNoDupes = 0)
    Local $iEnd, $iPerms = 1, $iDivisor
    If $iBase Then
        $iEnd = $aArray[0]
    Else
        $iEnd = UBound($aArray) - 1
    EndIf
    For $i = 2 To $iEnd ; count permutations
        $iPerms *= $i
    Next
    If $iNoDupes Then
        For $x = $iBase to $iEnd ; reduce array size for each dupe
            If Not $aArray[$x] Then ContinueLoop
            $iDivisor = 2
            For $y = $x + 1 to $iEnd
                If $aArray[$y] = $aArray[$x] Then
                    $iPerms /= $iDivisor
                 $aArray[$y] = ""
                 $iDivisor += 1
                EndIf
            Next
        Next
    EndIf
    Return $iPerms
EndFunc

Actually, considering what you just said in your prior post, I think you'd find that thread of interest:

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×