TGoofnik
BAN USERWell, I just noticed that my code only handles permutations of the i'th string as substrings in the ( i+1) string. permutations are only a subset of anagrams.
I used the karp-rabin like approach, by using a 'sum of characters' hash, because a string and its permutations have the same hash value with this hash. I roll this hash when the i+1 string is larger then the i'th string.
Finally, because a sum of chars hash can have lots of multiple hits, if the hashes are equal, I verify that it is a permutation, by taking every character in the original string, and removing it in the candidate substring. If I found all the characters and removed them in the candidate, it is a permutation.
def printOption( option ):
output = "[ "
for item in option:
output += "{0},".format( str(item) )
print output.rstrip( ',' ) + " ]"
def getSumSets( input, sum, option ):
for int in input:
option.append( int )
if sum - int == 0:
printOption( option )
elif sum - int > 0:
getSumSets( input[input.index(int)+1:], sum - int, option )
option.pop()
if __name__ == "__main__":
input = [ 1, 3, 4, 5, 6, 15 ]
getSumSets( input, 15, [] )
And with a simple sum hash:
import sys
def hash( wholeString ):
sum = 0;
for char in wholeString:
sum += ord( char )
return sum
def rollhash( prev, next , current ):
return current - ord(prev) + ord(next)
def anagram( src, dst ):
try:
dst = list(dst)
for char in src:
del dst[dst.index( char )]
except:
return False
return True
if __name__ == "__main__":
input = sys.argv[1:]
count = 0
for i in range( len( input ) - 1 ):
if len( input[i] ) > len( input[i+1] ):
continue
patternHash = hash( input[i] )
subhash = 0
for j in range( len( input[i+1] ) - len(input[i]) + 1 ):
substr = input[i+1][j:j + len(input[i])]
if j == 0:
subhash = hash( substr )
else:
subhash = rollhash( input[i+1][j-1], input[i+1][j + len(input[i]) - 1], subhash )
if patternHash == subhash and \
anagram( input[i], input[i+1][j:j + len(input[i])] ):
count += 1
print count
static void Main( string[] args )
{
int[] A = { 1, 2, 3, 6, 10 };
int[] B = { 1, 4, 5, 7 };
int k = 12;
findMinSumPair( A, B, k );
Console.ReadLine();
}
public class pairComparer : IComparer<Tuple<int, int>>
{
public int Compare( Tuple<int, int> x, Tuple<int, int> y )
{
if ( x.Item1 + x.Item2 < y.Item1 + y.Item2 )
return -1;
else if ( x.Item1 + x.Item2 > y.Item1 + y.Item2 )
return 1;
return 0;
}
}
static void findMinSumPair( int[] A, int[] B, int k )
{
List<Tuple<int, int>> all = new List<Tuple<int, int>>();
int i = 0, j = 0;
while ( all.Count() < k )
{
for ( int l = j; l < B.Count(); ++l )
all.Add( Tuple.Create( A[i], B[l] ) );
for ( int l = i + 1; l < A.Count(); ++l )
{
all.Add( Tuple.Create( A[l], B[j] ) );
}
all.Sort( new pairComparer() );
i++;
j++;
}
for( int l = 0; l < k; ++l )
Console.WriteLine( $"( {all.ElementAt(l).Item1}, {all.ElementAt( l ).Item2} )" );
}
Replevijhoyt, Android Engineer at A9
Hello, I am working as a machine operator and we are working in manufacturing units and operate equipment to create ...
Repcarlawbartlett, Accountant at ASU
Managed a small team managing toy elephants for the underprivileged. A real dynamo when it comes to managing vashikaran mantra ...
Replouisefbray, Integration Software Engineer at Ask.com
Hey! My name is Louise and I am a computer hardware retailer and wholesaler.I also provide services online. My ...
RepEwaMariaa, Cloud Support Associate at Abs india pvt. ltd.
Hi, I am an Localization translator from New York,Travelling with company executives on foreign trips is the favorite part ...
If a black pixel has the value 1 and white pixel has the value 0, a O(mn) solution is:
- TGoofnik October 09, 2017