Jump to content

Way to make this faster?


jb09
 Share

Recommended Posts

I'm wanting to know all the possiblities of order of a set of numbers which have "a", "b", or "c" in front. Like:

"a1,a2,a3,a4,a5.......b1,b2,b3......c1,c2,c3.......c19,c20"

I understand _ArrayPermute(), yet the only orders I'm interested in must consist of have each series of numbers for each letter in order. Like: "a1,b1,a2,a3,c1....." and so forth. Not "a1,b1,a3,c1,a2" as "a3" is before "a2"

First off, I've made a work around so I don't recieve the error of exceeded array limit when using _ArrayPermute(). I made the function write to a .txt file instead of saving everything in array. Yet this would create a very very large file, which would be a problem opening. Therefore, I created an additional function to "check" the order where the numbers are in order. Now to the question I need help in. Is it possible to rewrite this so the script computes faster?

Here is my redone _ArrayPermute() and _ArrayExeterInternal()

Func ArrayPermute(ByRef $avArray, $sDelim = ",")
If Not IsArray($avArray) Then Return SetError(1, 0, 0)
If UBound($avArray, 0) <> 1 Then Return SetError(2, 0, 0)
Local $iSize = UBound($avArray), $aIdx[$iSize], $aResult=""
For $i = 0 To $iSize - 1
  $aIdx[$i] = $i
Next
Array_ExeterInternal($avArray, 0, $iSize, $sDelim, $aIdx, $aResult)
EndFunc

Func Array_ExeterInternal(ByRef $avArray, $iStart, $iSize, $sDelim, ByRef $aIdx, ByRef $aResult)
If $iStart == $iSize - 1 Then
  For $i = 0 To $iSize - 1
   $aResult &= $avArray[$aIdx[$i]] & $sDelim
  Next
  If $sDelim <> "" Then $aResult = StringTrimRight($aResult, 1)
  If CheckOrder($aResult) Then FileWriteLine($file, $aResult)
  $aResult = ""
Else
  Local $iTemp
  For $i = $iStart To $iSize - 1
   $iTemp = $aIdx[$i]
   $aIdx[$i] = $aIdx[$iStart]
   $aIdx[$iStart] = $iTemp
   Array_ExeterInternal($avArray, $iStart + 1, $iSize, $sDelim, $aIdx, $aResult)
   $aIdx[$iStart] = $aIdx[$i]
   $aIdx[$i] = $iTemp
  Next
EndIf
EndFunc

And my checkorder()

Func CheckOrder($string)
Local $test = StringSplit($string, ",", 2)
$t = 0
$acounter=0
$bcounter = 0
$ccounter = 0
While $t < UBound($test)
  $subtarray = StringSplit($test[$t],"",2)
  $stringt = StringTrimLeft($test[$t], 1)
  $int = Int($stringt) - 1
  If $subtarray[0] = "m" And $int = $acounter Then
   $acounter = $acounter + 1
  ElseIf $subtarray[0] = "c" And $int = $bcounter Then
   $bcounter = $bcounter + 1
  ElseIf $subtarray[0] = "d" And $int = $ccounter Then
   $ccounter = $ccounter + 1
  Else
   Return False
  EndIf
  $t = $t + 1
WEnd
Return True
EndFunc

Oh, and there are 20 numbers to each letter. Your help will be much appreciated.

Edited by jb09
Link to comment
Share on other sites

  • Replies 94
  • Created
  • Last Reply

Top Posters In This Topic

Top Posters In This Topic

I'm wanting to know all the possiblities of order of a set of numbers which have "a", "b", or "c" in front. Like:

"a1,a2,a3,a4,a5.......b1,b2,b3......c1,c2,c3.......c19,c20"

If I understand you correctly, I would do something like this.

#include <Array.au3>

Local $aRet[26*20], $iCount = 0, _
$aAlpha[26] = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

For $i = 0 To 25
    For $j = 1 To 20
        $aRet[$iCount] = $aAlpha[$i] & $j
        $iCount += 1
    Next
Next
_ArrayDisplay($aRet)
Link to comment
Share on other sites

If I understand you correctly, I would do something like this.

No, I'm afraid you didn't understand me. I already have an array with the letters and numbers, which I'm only doing 3 letters. I'm wanting to find out all the possible set of series with each number in corresponding order.

For example on smaller scale:

"a1,b1,c1,a2,b2,c2,a3,b3,c3" is ok

"b1,a1,b2,c1,a2,a3,c2,b3,c3" is ok

"b1,c1,a2,c2,c3,b3,a1,b2,a3" is not ok

Just noticed I mispelled in the thread title. Should be "Way" not "Why".

Link to comment
Share on other sites

kylomas,

Via looking at the example again to make sure _arraysort did what I thought, I see no use for it considering what I'm trying to do. I think, I haven't tested, _arraysort would give me the same list over and over.

Link to comment
Share on other sites

Ah, I think I get what you mean now. The order of letters doesn't matter, so long as A3 does not occur before A2 (or B10 before B1 etc...). That's kind of complicated.

Edit

So the last example you gave:

"b1,c1,a2,c2,c3,b3,a1,b2,a3"

is not ok because a2 occurs before a1, and (also) b3 occurs before b2.

however

c1...c2, c3 occur in sequence.

Edited by czardas
Link to comment
Share on other sites

Ah, I think I get what you mean now. The order of letters doesn't matter, so long as A3 does not occur before A2 (or B10 before B1 etc...). That's kind of complicated.

Exactly what I want. Sadly I'm starting to find out it is complicated.

Link to comment
Share on other sites

See Edits...

EDIT: I am assuming you do not care about the letter, it's just the number that matters (based on your examples)

EDIT2: Learning to read :oops:

Well I just reread the thread and I was completely wrong in what you were asking for, as all mine does is sort the array based on the numbers only... removing my script to avoid confusing others trying to help.

kylomas,

Via looking at the example again to make sure _arraysort did what I thought, I see no use for it considering what I'm trying to do. I think, I haven't tested, _arraysort would give me the same list over and over.

EDIT 74: Decided to post the code () just in case that IS what the OP was looking for.

Edited by danwilli
Link to comment
Share on other sites

jb09,

I am not clear about "all the possible sets of series". Given the set "1,2,3", "all the possible sets of series" is

"1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2" and "3,2,1", however, this doe not seem to be what you really want. Based on your example you want a series sorted by letter within number, such as, "a1, b1, a2, a3, d4, a5, b5, g5...etc". Is this correct?

kylomas

Forum Rules         Procedure for posting code

"I like pigs.  Dogs look up to us.  Cats look down on us.  Pigs treat us as equals."

- Sir Winston Churchill

Link to comment
Share on other sites

jb09,

danwilli posted while I was typing...his solution is PRECICELY what I think you are asking for...Good job daniwlli!!

kylomas

Haha, I just removed it thinking it was NOT what he was asking for LOL

I think he is asking for basically what I did, order the array based on number, BUT he wants EVERY POSSIBLE sorting without breaking the rules of the numbers being sorted.

OP, is this correct? Can you clarify what you want please... are you asking for a sort or are you asking for EVERY POSSIBLE combination available without breaking the rules of numbers being out of order?

EDIT: If all you are looking for is to sort the array based on number only, this is what I had posted, but I doubt it is what you want:

#include <Array.au3>
Dim $array[100]
Dim $Char[4] = ['a', 'b', 'c', 'd']
For $a = 0 To 99
    $array[$a] = $Char[Int(Random(0,3))] & Int(Random(1, 50))
Next
_ArrayDisplay($array, "Before Sorting")
_Sort($array)
_ArrayDisplay($array, "After Sorting")

Func _Sort(ByRef $aSort, $NumDigits = 2)
    Local $atest[UBound($aSort)][2]
    For $a = 0 To UBound($aSort) - 1
        $atest[$a][0] = $aSort[$a]
        $atest[$a][1] = StringFormat("%.9d", StringRegExpReplace($aSort[$a],'D', ''))
    Next
    _ArraySort($atest, 0, 0, 0, 1)
    For $a = 0 To UBound($aSort) - 1
        $aSort[$a] = $atest[$a][0]
    Next
EndFunc

If you are looking for every possible combination of sorting while following the rules of sorting by number, we will have to wait for somebody else to come along and dazzle us, because that is well beyond my abilities (or at least well beyond just writing it real quick for you)

Edited by danwilli
Link to comment
Share on other sites

@danwilli,

I will look forward to seeing the code that will produce every possible combination of letters within each number, in collating sequence, however, as I said, I think you produced what he wants.

Either way, can't do much if jb09 does'nt join the game!!

kylomas

Forum Rules         Procedure for posting code

"I like pigs.  Dogs look up to us.  Cats look down on us.  Pigs treat us as equals."

- Sir Winston Churchill

Link to comment
Share on other sites

With something like this, you quickly realize that the number of permutations are much too large. Writing to disk is the only option and it is still going to be a long process. It is possible to speed things up by eliminating some unnecessary steps. I have scaled this problem down (a lot) to illustrate a possible approach. Firstly creating all permutations is not a good idea since you will eventually eliminate most of them. That's a lot of unneeded processing.

I have not completely solved the problem, but I have changed its nature. Now the problem is how to create a function that generates permutations excluding any duplicate arrangements. Anyway the code below illustrates how the processing can possibly be speeded up. Please note that the functions _ArrayPermute and _ArrayUnique need to be improved (speedwise) and preferably combined for this to be an efficient approach. The code below should be self-explanatory.

#include <Array.au3>

Dim $aArray[6] = ["a","a","b","b","c","c"]

$aNewArray = _ArrayPermute($aArray, ",") ; Produces too many unwanted duplicate patterns.
_ArrayDisplay($aNewArray, "Array Permuted")
_ArrayDelete($aNewArray, 0)

$aNewArray = _ArrayUnique($aNewArray) ; Remove repeat patterns.
_ArrayDisplay($aNewArray, "Array Unique")

; Now we add the numbers in the correct order.
Dim $aTemp
For $i = 1 To $aNewArray[0]
    $a = 1
    $b = 1
    $c = 1
    $aTemp = StringSplit($aNewArray[$i],",",2)
    For $j = 0 To UBound($aTemp) -1
        Switch $aTemp[$j]
            Case "a"
                $aTemp[$j] &= $a ; Append the next numeric value for A
                $a += 1 ; Increment the numeric value each time.
            Case "b"
                $aTemp[$j] &= $b
                $b += 1
            Case "c"
                $aTemp[$j] &= $c
                $c += 1
        EndSwitch
        $aNewArray[$i] = _ArrayToString($aTemp, ",")
    Next
Next
_ArrayDisplay($aNewArray, "Final Array")

Edit

The code's a bit rough and ready, but I hope it will be useful as an illustration.

Edited by czardas
Link to comment
Share on other sites

Nicely done czardas, I think that is what the OP is after. _ArrayPermute() scares me LOL, but you did a fantastic job that I'm pretty sure will lead the OP in the right direction. Re reading the first post again, I KNOW that what I wrote isn't what he is after, but I'm pretty sure you nailed it, or at least gave him a good template.

:oops:

Link to comment
Share on other sites

czardas,

I think your on the right track, I want to figure out what arrayunique does. As I don't remember but I have played with it before.

@danwilli, yeah now you know what I want.

Sorry, had college class.

Edit: WOW, incredible idea. make all permutes with just letters, remove duplicates, then add numbers to them. Amazing.

Only thing is, not enough room to do in an array. Let me get this out, I let this script run overnight writing to a file without the checkorder function. The file was 25 gigs and still not finished. Text editors I couldn't get to open the file, so idk at what point autoit was at. Would autoit still be able to open the file with fileopen? Or is there a way to just reset to first line without re-opening the file?

@czardas,

Second what danwilli said. Would be nice to see what the OP's input is and what he does before calling his funcitons...

kylomas

Only thing I was doing was creating an array to be put into the functions. Doing so by loops, if you need to see that code I'll be glad to post it. Which czardas's code would do away with those loops.

Edited by jb09
Link to comment
Share on other sites

I'm still thinking about the size limitation issue. The duplicates need removing within the permutation function to limit the exponential growth of the results. The numbers you have appear (to me) to be way off the richter scale, as is often the case with permutations. In fact I have thought of one or two possible ways to avoid duplication and limit the size of the data, but it still won't be anywhere near enough to do what you ask with arrays. I could be wrong, but I suspect you won't get beyond single digits A1 to A9, and even then the method will need to be kind of crafty to achieve thiis.

Perhaps using a database to store results is a possiblity., but I don't know much about the _SQLite functions.

Edited by czardas
Link to comment
Share on other sites

jb09,

I'll poke this bear one more time. The following produces an ordered list where all combinations are present in collating sequence with succeeding numbers greater than preceeding numbers.

;
;
;
#include <array.au3>
Local $str, $a10
For $i = 1 To 20
 For $j = $i To 20
  For $k = $j To 20
   For $l = $k To 20
    $str &= "A" & $i & ',' & "B" & $j & ',' & "C" & $k & ',' & "D" & $l & @CRLF
   Next
  Next
 Next
Next
$a10 = StringSplit($str,@crlf,3)
_arraydisplay($a10)

This does not "permute" all letters within numbers, if that is indeed what you want, but may give you some ideas for another approach to solve the problem.

Good Luck,

kylomas

Forum Rules         Procedure for posting code

"I like pigs.  Dogs look up to us.  Cats look down on us.  Pigs treat us as equals."

- Sir Winston Churchill

Link to comment
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
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...