Velocity Reviews > How to generate k+1 length strings from a list of k length strings?

# How to generate k+1 length strings from a list of k length strings?

Girish Sahani
Guest
Posts: n/a

 06-08-2006

I have a list of strings all of length k. For every pair of k length
strings which have k-1 characters in common, i want to generate a k+1
length string(the k-1 common characters + 2 not common characters).
e.g i want to join 'abcd' with bcde' to get 'abcde' but i dont want to
join 'abcd' with 'cdef'
Currently i'm joining every 2 strings, then removing duplicate characters
from every joined string and finally removing all those strings whose
length != k+1.Here's the code i've written:

for i in range(0,len(prunedK) - 1,1):
if k in range(1,len(prunedK),1) & i+k <= len(prunedK) -1:
colocn = prunedK[i] + prunedK[i+k]
prunedNew1.append(colocn)
continue
for string in prunedNew1:
stringNew = withoutDup(string)
prunedNew.append(stringNew)
continue

But this one is quite bad in the time aspect .
girish

MTD
Guest
Posts: n/a

 06-08-2006
Try this:

def k2k1(string1, string2):
for c in string1:
string2 = string2.replace(c,"",1)

if len(string2) == 1:
string1 += string2

return string1

print k2k1("abcd", "ebcd")

MTD
Guest
Posts: n/a

 06-08-2006
actually, minor fix:

MTD wrote:
> Try this:
>
> def k2k1(string1, string2):
> for c in string1:
> string2 = string2.replace(c,"",1)
>
> if len(string2) == 1:
> string1 += string2

else:
string1 = ""

>
> return string1
>
> print k2k1("abcd", "ebcd")

MTD
Guest
Posts: n/a

 06-08-2006
So yeah, just to put it all together, try this. From your two Ks, it
either returns K+1 if it can or an empty string.

def k2k1(string1, string2):
for c in string1:
string2 = string2.replace(c,"",1)

if len(string2) == 1:
string1 += string2
else:
string1 = ""

return string1

Testing:

gives:

Jon Clements
Guest
Posts: n/a

 06-08-2006
Are you asking the question, "Which pairs of strings have one character
different in each?", or "Which pairs of strings have a substring of
len(string) - 1 in common?".

Jon.

Girish Sahani wrote:
> I have a list of strings all of length k. For every pair of k length
> strings which have k-1 characters in common, i want to generate a k+1
> length string(the k-1 common characters + 2 not common characters).
> e.g i want to join 'abcd' with bcde' to get 'abcde' but i dont want to
> join 'abcd' with 'cdef'
> Currently i'm joining every 2 strings, then removing duplicate characters
> from every joined string and finally removing all those strings whose
> length != k+1.Here's the code i've written:
>
> for i in range(0,len(prunedK) - 1,1):
> if k in range(1,len(prunedK),1) & i+k <= len(prunedK) -1:
> colocn = prunedK[i] + prunedK[i+k]
> prunedNew1.append(colocn)
> continue
> for string in prunedNew1:
> stringNew = withoutDup(string)
> prunedNew.append(stringNew)
> continue
>
> But this one is quite bad in the time aspect .
> girish

Boris Borcic
Guest
Posts: n/a

 06-08-2006
Girish Sahani wrote:
> I have a list of strings all of length k. For every pair of k length
> strings which have k-1 characters in common, i want to generate a k+1
> length string(the k-1 common characters + 2 not common characters).
> e.g i want to join 'abcd' with bcde' to get 'abcde' but i dont want to
> join 'abcd' with 'cdef'
> Currently i'm joining every 2 strings, then removing duplicate characters
> from every joined string and finally removing all those strings whose
> length != k+1.

Hum, since your code is not syntactically correct, anything will run faster
I'd favor the following, that I find most readable

sets = map(set,list_of_strings)
res = set(''.join(sorted(s1|s2)) for s1 in sets for s2 in sets if len(s1^s2)==2)

unless performance is really an issue

Here's the code i've written:
>
> for i in range(0,len(prunedK) - 1,1):
> if k in range(1,len(prunedK),1) & i+k <= len(prunedK) -1:
> colocn = prunedK[i] + prunedK[i+k]
> prunedNew1.append(colocn)
> continue
> for string in prunedNew1:
> stringNew = withoutDup(string)
> prunedNew.append(stringNew)
> continue
>
> But this one is quite bad in the time aspect

how do you know ?

> girish

you should do your own homework

MTD
Guest
Posts: n/a

 06-08-2006

Jon Clements wrote:
> Are you asking the question, "Which pairs of strings have one character
> different in each?", or "Which pairs of strings have a substring of
> len(string) - 1 in common?".
>
> Jon.

I imagine it's the former because the latter is trivially easy, I mean
_really_ trivially easy.

bearophileHUGS@lycos.com
Guest
Posts: n/a

 06-08-2006
Boris Borcic:
> I'd favor the following, that I find most readable
> sets = map(set,list_of_strings)
> res = set(''.join(sorted(s1|s2)) for s1 in sets for s2 in sets if len(s1^s2)==2)

I think there can be written more readable code. For my programs I
usually prefer simpler code, that (if possible) even a children can
understand. So I can debug, modify and improve it better & faster.

Bye,
bearophile

bearophileHUGS@lycos.com
Guest
Posts: n/a

 06-08-2006
> I think there can be written more readable code. For my programs I
> usually prefer simpler code, that (if possible) even a children can
> understand. So I can debug, modify and improve it better & faster.

Debugged:
I think it can be written more readable code.
In this newsgroup sometimes I have tried to post 'clever' code, but for
my programs I (if possible) prefer simpler code, that even a child can
understand. So I can debug, modify and improve it faster.

Sorry, I was tired,
bearophile

Boris Borcic
Guest
Posts: n/a

 06-08-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Boris Borcic:
>> I'd favor the following, that I find most readable
>> sets = map(set,list_of_strings)
>> res = set(''.join(sorted(s1|s2)) for s1 in sets for s2 in sets if len(s1^s2)==2)

>
> I think there can be written more readable code.

readability, of course, is in the eye of the beholder... and I find this code
*much* easier to recognize as a realisation of the description made by the OP,
than the code he himself offered - if you care to take a look at both.

For my programs I
> usually prefer simpler code,

I challenge you to write simpler code to do the equivalent.

> that (if possible) even a children can
> understand.

what child ? one that is trained just like *you* think children should start, I
guess.

> So I can debug, modify and improve it better & faster.

Sure, but the case is we each were *distinct* children.

>
> Bye,
> bearophile
>