[SOLVED] Factorial & get all possible variations?

[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 October 9, 2012 by caleb41610

[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

[Melba23]

caleb41610,

Perhaps this might help:

#include <Array.au3>

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

M23

[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.

[caleb41610]

caleb41610,

Perhaps this might help:

#include <Array.au3>

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

M23

Well look at that.. I didn't find it when I searched for "string permutation"

Thanks!

[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.

[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"!

M23

[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. 2⁶⁴ 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 October 10, 2012 by jchd

[Spiff59]

My question would be...

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

Or only 3?

[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.

[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):

expandcollapse popup

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: