Every few months, I return to Project Euler and try to solve one using Xojo (very much as a very old and amateur coder).
I am presently working on a problem where I want to check if a string of numbers is a permutation of another string of numbers.
Naively, I can achieve this by turning them both into arrays, sorting the arrays, turning them back into strings and then using string compare to see if they are identical.
This is fine for a one off, but unworkable for a Project Euler puzzle that makes me check a million of them!
I think I am looking for a string.sort function (cannot see one in MBS either). I have drawn a blank for what I would have thought must be a reasonably common problem. Could any kind soul offer a pathway please?
Here is an idea that couls perhaps speed-up the algorithm: add up the individual numbers making the string. Then If the sum is equal to the sum of the reference string members, I would perform the array comparison.
The idea is that permutations will yield the same total. You then have to make sure that you don’t have a false positive (like 1238 and 1247) by checking the individual sorted array members.
I am not entirely sure that this would be faster, but intuitively, it seems faster.
Sorting the strings isn’t really necessary. After checking that both strings are the same length I would use two arrays for counting the occurrences of each number (I assume you mean digit) in the reference and the comparison string. First this is done for the reference string, and for counting the occurrences in the comparison string I would walk through the string and for each digit I would check whether its occurrences so far are equal to those in the reference string. If they are – and I am about to add another occurrence – then the digit occurs more often in the comparison string than in the reference string so I can stop and return false. But if I get to the end of the string without this happening then all the counters are guaranteed to be equal and both strings are permutations of each other.
Start with an array 10 elements, one for each digit. For the first string, increment the element for each matching digit. So if the digit is a 9, do Counter(9) = Counter(9) + 1. Then for the second string, do the same thing except decrement. If the array is all zeroes, then you’ve got a permutation.
Many thanks for the idea and it does save a a tiny bit - I timed it as about 8 milliseconds improvement over 1 million iterations so not the ‘gamechanger’ I am seeking.
I agree that Thom’s idea should be faster. Did you try a variation on Thom’s idea? I am thinking this: Fill the reference array once. Count occurrences of digits in a test array for a string. Compare the test array with the reference array. To compare, I would convert the arrays to string and compare the strings. Of course, the reference array would be converted back to a string just once. Repeat for each string to be tested. I think that it would save processing time. I suspect that aggressive compiling would have an impact here. Or, I never actually tried this, compare the arrays directly as in Ref() = Test(). Not sure that this actually works though. Thom’s approach to count the digits in a 10-member array makes a lot of sense and does not require sorting at all.
You could combine my idea and Thom’s suggestion that uses just one array rather than two: You would check whether the counter you are about to decrement is already zero; in that case the strings cannot be permutations of each other and you can stop to return false. In the end you could simply return true; checking whether all the array elements are zero will be superfluous: Since the total number of digits is the same in both strings and none of the digits occur more often in the second string than they do in the first, the converse must also be true.
By the way, the reason I was suggesting using two arrays was that you could also test one string against all the others and would only need to count the digits in the first string once. This would be advantageous if you wanted to find all sets of strings that are permutations of each other rather than just checking two strings. For the latter task, the one array solution would arguably be the better one.
Somewhat nervous about posting my pathetic attempts at code, but I suppose the only way to learn etc etc.
Here is my function to implement Thom’s suggestion. I am sure it can be improved….
Only integers with the same number of digits are passed to it
Function IspermNew(x as integer, y as integer) As boolean
Var check() As Integer = array(0,0,0,0,0,0,0,0,0,0)
Var a As String = x.tostring
Var b As String = y.tostring
Var i,t As Integer
For i = 0 To a.length-1
t = a.middle(i,1).ToInteger
check(t) = check(t) +1
Next i
For i = 0 To b.length-1
t = b.middle(i,1).ToInteger
check(t) = check(t) - 1
Next i
For i = 0 To 9
If check(i) <> 0 Then
Return False
End If
Next i
Return True
I’m still trying to figure out where the issue is, but so far I’m seeing what Larry is seeing. Sorting and comparing is taking an average of 48 microseconds, counting digits is taking an average of 330 microseconds.
Ok as I expected, converting to string was to blame. Here’s a version that is cutting my time down dramatically:
If Value1 = Value2 Then
Return True
End If
Var Counts(9) As Integer
For Place As Integer = 1 To 20
Var Digit As Double = Value1 / 10
Value1 = Digit
Digit = Round((Digit - Value1) * 10)
Counts(Digit) = Counts(Digit) + 1
Next
For Place As Integer = 1 To 20
Var Digit As Double = Value2 / 10
Value2 = Digit
Digit = Round((Digit - Value2) * 10)
Counts(Digit) = Counts(Digit) - 1
Next
For Idx As Integer = 0 To 9
If Counts(Idx) <> 0 Then
Return False
End If
Next
Return True
This is not as fast as it could be if you add in aggressive compilation, turning off bounds checking, and reducing the number of places being checked if you know the max value. I wanted to avoid Round but floating point math is a funny thing and the algorithm won’t work without it.
In my latest test with 1,000,000 iterations, I got an average time of 46 microseconds with sorting and 12 microseconds with this technique in debug mode.
This performs well on Apple Silicon. I would have thought the character manipulation would be a slow down. The attached project has some benchmarking.
Var i, pos As Integer
Var s1a() As String = x.ToString.Split("")
Var s2a() As String = y.ToString.Split("")
For i = 0 To s1a.LastIndex
pos=s2a.IndexOf(s1a(i))
If pos= -1 Then
Exit
Else ' take it out of the running
s2a(pos)=""
End If
Next
Return i>s1a.LastIndex
In a built app, the results get really impressive. 44.76 microseconds for sorting, 0.58 microseconds for counting. Meaning around half a second to run a million tests. It’s also interesting that counting saw roughly a 20x speed improvement in a built app, but sorting saw nearly no improvement at all.
I’ve checked whether my suggestion would improve things: If the numbers are indeed permutations of each other the speed-up is negligible. If they are not then my version can be up to 50% faster (depending on how different the digits are) which may or may not be relevant. If one used strings of digits rather than integers to remove any size limits the speed-up would probably be larger for longer strings.
In any case I prefer my version as it simplifies the code. One only needs to insert if Counts(Digit) = 0 then return False before the last line of the second For loop while the third For loop (checking whether all the counters are zero) can be removed altogether.
Using strings in any capacity is going to kill performance. If you wanted to limit the number of digits checked, you could use a loop:
Var NumDigits As Integer
For Num As Integer = 1 To 20
If Value1 < Pow(10, Num) Then
NumDigits = Num
Exit
End If
Next
I’m not confident it would be worth doing, but I haven’t tested it.
Checking for zero in the second loop is a great idea… unless you have repeat digits. Just because it’s not yet zero doesn’t mean it won’t become zero later.
A very simple change brings the average CountDigits time down to 0.32 microseconds. We don’t need to count every digit up to 20 places, only until there are no more digits left.
#Pragma DisableBoundsChecking True
#Pragma DisableBackgroundTasks True
If Value1 = Value2 Then
Return True
End If
Var Counts(9) As Integer
For Place As Integer = 1 To 20
Var Digit As Double = Value1 / 10
Value1 = Digit
Digit = Round((Digit - Value1) * 10)
Counts(Digit) = Counts(Digit) + 1
If Value1 = 0 Then
Exit
End If
Next
For Place As Integer = 1 To 20
Var Digit As Double = Value2 / 10
Value2 = Digit
Digit = Round((Digit - Value2) * 10)
Counts(Digit) = Counts(Digit) - 1
If Value2 = 0 Then
Exit
End If
Next
For Idx As Integer = 0 To 9
If Counts(Idx) <> 0 Then
Return False
End If
Next
Return True