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 karprabin 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, [] )

TGoofnik
October 07, 2017 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][j1], 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

TGoofnik
October 06, 2017 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} )" );
}

TGoofnik
September 09, 2017
Repcarlawbartlett, Accountant at ASU
Managed a small team managing toy elephants for the underprivileged. A real dynamo when it comes to managing vashikaran mantra ...
Open Chat in New Window
If a black pixel has the value 1 and white pixel has the value 0, a O(mn) solution is:
 TGoofnik October 09, 2017