Sign in to follow this  
Followers 0

Way to make this faster?

95 posts in this topic

Posted (edited)

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

Share this post


Link to post
Share on other sites



Posted

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)

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted (edited)

jb09,

and _arraysort does not work????

kylomas

edit:question - are you saying that you want to order series by letter within number?

Edited by kylomas

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted (edited)

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

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted (edited)

I need to think about this. No guarantees that I'll come up with an answer. I bet some French guy I know could figure this out in seconds. :oops:

Edited by czardas

Share this post


Link to post
Share on other sites

Posted (edited)

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

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted

jb09,

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

kylomas

Share this post


Link to post
Share on other sites

Posted (edited)

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

Share this post


Link to post
Share on other sites

Posted

@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

Share this post


Link to post
Share on other sites

Posted (edited)

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

Share this post


Link to post
Share on other sites

Posted

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:

Share this post


Link to post
Share on other sites

Posted

@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

Share this post


Link to post
Share on other sites

Posted

Thanks guys: let's hope you're right. It certainly got me thinking, so that's something al least. :oops:

Share this post


Link to post
Share on other sites

Posted (edited)

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

Share this post


Link to post
Share on other sites

Posted (edited)

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

Share this post


Link to post
Share on other sites

Posted

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

Share this post


Link to post
Share on other sites

Posted (edited)

I would love to work on an ArrayPermuteUnique() function because I think i's very interesting. Unfortunately I have a lot on my plate right now, so I wouldn't be able to give it enough attention. I would like to know how much it is possible to circumvent memory limitations by removing duplicates as you go along. I think it's a worthy challenge for anyone with time on their hands. It's the only missing element from the code I

Edited by czardas

Share this post


Link to post
Share on other sites

Posted

jb09,

"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

Why is "c1" ok in line #2???

kylomas

Share this post


Link to post
Share on other sites

Posted

@czardas,

I clearly do not understand the problem yet. Can you answer my question from post #22?

kylomas

Share this post


Link to post
Share on other sites

Posted

@czardas,

I clearly do not understand the problem yet. Can you answer my question from post #22?

It is the first occurence of 'c' in the string. See this

Share this post


Link to post
Share on other sites

Posted (edited)

jb09,

Why is "c1" ok in line #2???

kylomas

"c1" is ok because it is the first occurence of the letter "c". I'm not sure how else to explain the "rules" as to what I'm looking for.

@czardas,

I'll give it a try on making the arraypermuteunique(), but quite frankly I feel like I'm finally getting in over my head. I'll try to learn the SQLite stuff first. Much apprecitiated on the help and guidance.

Edit:

An idea just hit me. To use arraypermute we have to stay under 16 million elements, which would be 10 elements being entered into the function have some 3 million elements. Using your code, then finds all duplicates and removes the extras. Now, for my purposes, instead of starting with 10 I start with 9, three of each letter. This would give me only the possible combinations of a1-a3, b1-b3, and c1-c3, just without the numbers added. Now, lets call this array "Permuted1". What if......

We don't had the numbers to this array....instead first use arraypermute again, only with 7 elements from Permuted1? Of course doing so a few times if and probably are more than 7 elements in Permuted1. (I'm currently running this setup of 9 original elements to find out, as I write this arrayunique is running removing duplicates. ) Now lets call the array, from our second arraypermute series into one, "Permuted2". And call the function arrayunique on Permuted2. Last but not least add the numbers to Permuted2. Would this be quicker? Plus, considering the final information I'm after from this list of combinations, I know I won't be worried about having more than three of the same letter in a row. It could be possible that having only 4 a's in a row the very first thing in the combination which would be my final answer for the script after this. But I doubt it. If so it should be easy to get the combinations with 4 a's first. So in the end I'm also eliminating some data which I won't need.

Comments?

I should be fine coding this setup, just wanting input before I do.

Edited by jb09

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  
Followers 0