1

I want to implement an algorithm that gets the index of letter changes. I have the below list, here I want to find the beginning of every letter changes and put a result list except the first one. Because, for the first one, we should get the last index of occurrence of it. Let me give you an example: 

letters=['A','A','A','A','A','A','A','A','A','A','A','A','B','C','C','X','D','X','B','B','A','A','A','A']

Transitions: 

 'A','A','A','A','A','A','A','A','A','A','A','A'-->'B'-->'C','C'-->'X'-->'D'-->'X'-->'B','B'-->'A','A','A','A'

Here, after A letters finish, B starts, we should put the index of last A and the index of first B and so on, but we should not include X letter into the result list.
Desired result:

  [(11, 'A'), (12, 'B'), (13, 'C'), (16, 'D'), (18, 'B'), (20, 'A')]

So far, I have done this code, this finds other items except the (11, 'A'). How can I modify my code to get the desired result? 

for i in range(len(letters)):
    if letters[i]!='X' and letters[i]!=letters[i-1]:
        result.append((i,(letters[i])))

My result: 

[(12, 'B'), (13, 'C'), (16, 'D'), (18, 'B'), (20, 'A')] ---> missing (11, 'A').
Improve this question
23
  • Not the nicest fix, but you could add an 'X' to the start of the list before the loop. That could fix it. Commented Aug 1, 2013 at 19:50
  • Yea, you can't access i-1 when you're on the first one. So it won't append there. Instead try doing i+1 == i, and range(len(letters)-1) Commented Aug 1, 2013 at 19:50
  • OP, I don't think your desired results are consistent. Last B is 20 not 18. 18 is X Commented Aug 1, 2013 at 20:19
  • 1
    agree with @sihrc. I'm struggling to understand what the desired result is. why is (16, 'D') in the results but not (14, 'C')? Also, OP should make a list that is clearer to read (e.g., why repeating 'A' more than twice?). Commented Aug 1, 2013 at 20:26
  • 1
    @CoKoder If you don't want the Xs, why not just filter them out at the very beginning? Commented Aug 1, 2013 at 20:29

8 Answers 8

Reset to default
3

Now that you've explained you want the first index of every letter after the first, here's a one-liner:

letters=['A','A','A','A','A','A','A','A','A','A','A','A','B','C','C','X','D','X','B','B','A','A','A','A']
[(n+1, b) for (n, (a,b)) in enumerate(zip(letters,letters[1:])) if a!=b and b!='X']
#=> [(12, 'B'), (13, 'C'), (16, 'D'), (18, 'B'), (20, 'A')]

Now, your first entry is different. For this, you need to use a recipe which finds the last index of each item:

import itertools
grouped = [(len(list(g))-1,k) for k,g in (itertools.groupby(letters))]
weird_transitions = [grouped[0]] + [(n+1, b) for (n, (a,b)) in enumerate(zip(letters,letters[1:])) if a!=b and b!='X']
#=> [(11, 'A'), (12, 'B'), (13, 'C'), (16, 'D'), (18, 'B'), (20, 'A')]

Of course, you could avoid creating the whole list of grouped, because you only ever use the first item from groupby. I leave that as an exercise for the reader.

This will also give you an X as the first item, if X is the first (set of) items. Because you say nothing about what you're doing, or why the Xs are there, but omitted, I can't figure out if that's the right behaviour or not. If it's not, then probably use my entire other recipe (in my other answer), and then take the first item from that.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

sihrc rightly pointed out in comments above that -- if we generalize slightly -- the last index of the first item is not 1 less than the first index of the second item in the case where the second item in the original list is the ignored item. This does, however, pass the single test case we've been given.
@JoshCaswell Hmm, in that case, I should combine this with my original groupby recipe.
I think groupby() will be the right first step towards solving whatever the problem turns out to actually be, yes. :)
@JoshCaswell Check it out. It's literally a munging of two inconsistent ways of finding transitions.
Hopefully that'll lay this to rest!
2

Your question is a bit confusing, but this code should do what you want.

firstChangeFound = False
for i in range(len(letters)):
    if letters[i]!='X' and letters[i]!=letters[i-1]:
        if not firstChangeFound:
            result.append((i-1, letters[i-1])) #Grab the last occurrence of the first character
            result.append((i, letters[i]))
            firstChangeFound = True
        else:
             result.append((i, letters[i]))
Improve this answer

5 Comments

This matches OP's desired results. +1
letters=['A','A','A','A','A','A','A','A','A','A','A','A','X','C','C','X','D','X','B','B','A','A','A','A'] . It prints [(12, 'X'), (13, 'C'), (16, 'D'), (18, 'B'), (20, 'A')] which is wrong since (12,'X') should be (11,'A').
@CoKoder If you have to complain on every single answer, then the problem is your question. In fact, this matches what you originally requested as your output.
@Marcin I am not complaining about it. What I want to say is that the answer should satisfy the other cases. It should not run for only a certain list,right?
You haven't presented any other cases, @CoKoder. You've given exactly one case, which this answer satisfies.
2

You want (Or, you don't, as you finally explained - see my other answer):

import itertools
import functional # get it from pypi
letters=['A','A','A','A','A','A','A','A','A','A','A','A','B','C','C','X','D','X','B','B','A','A','A','A']
grouped = [(len(list(g)),k) for k,g in (itertools.groupby(letters))]
#=> [(12, 'A'), (1, 'B'), (2, 'C'), (1, 'D'), (2, 'B'), (4, 'A')]
#-1 to take this from counts to indices
filter(lambda (a,b): b!='X',functional.scanl(lambda (a,b),(c,d): (a+c,d), (-1,'X'), grouped))
#=> [(11, 'A'), (12, 'B'), (14, 'C'), (16, 'D'), (19, 'B'), (23, 'A')]

This gives you the last index of each letter run, other than Xs. If you want the first index after the relevant letter, then switch the -1 to 0.

scanl is a reduce which returns intermediate results.

As a general rule, it makes sense to either filter first or last, unless that is for some reason expensive, or the filtering can easily be accomplished without increasing complexity.

Also, your code is relatively hard to read and understand, because you iterate by index. That's unusual in python, unless manipulating the index numerically. If you're visiting every item, it's usual to iterate directly.

Also, why do you want this particular format? It's usual to have the format as (unique item,data) because that can easily be placed in a dict.

Improve this answer

2 Comments

This is not what I want to do. It counts number of occurrences of each letter. But, I want to get the index of letter changes.
@CoKoder You might like to look at this now. With the addition of one line, it gives you the cumulative values (that is, indices).
1

With minimal change to your code, and following Josh Caswell's suggestion:

for i, letter in enumerate(letters[1:], 1):
    if letter != 'X' and letters[i] != letters[i-1]:
        result.append((i, letter))
first_change = result[0][0]
first_stretch = ''.join(letters[:first_change]).rstrip('X')
if first_stretch:
    result.insert(0, (len(first_stretch) - 1, first_stretch[-1]))
Improve this answer

5 Comments

This is cryptic. Also, does it properly handle the case where there's an X between the first non-X item, and the second?
Yes it does, but I agree the code could be cleaner. It was just a simple addition to what he already had.
@Marcin, Cleaned it up a bit. It has the advantage of not calculating all the groups for the last occurrence, so it should be significantly faster.
I think you could clean this up a little bit more, but it's reasonably concise as well as efficient. I already voted this up, so I can do no more. If you're really into the timing, then you can eliminate the redundant lookup.
@Marcin, Thanks. I did try to incorporate your techniques into my answer, because I appreciate the value of being idiomatic, but I didn't get very far. And as you say, I think it's now sufficiently concise and efficient.
1

Here's a solution which uses groupby to generate a single sequence from which both first and last indices can be extracted.

import itertools
import functools
letters = ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'C', 'X', 'D', 'X', 'B', 'B', 'A', 'A', 'A', 'A']

groupbysecond = functools.partial(itertools.groupby,key=operator.itemgetter(1))

def transitions(letters):
    #segregate transition and non-transition indices
    grouped = groupbysecond(enumerate(zip(letters,letters[1:])))
    # extract first such entry from each group
    firsts = (next(l) for k,l in grouped)
    # group those entries together - where multiple, there are first and last
    # indices of the run of letters
    regrouped = groupbysecond((n,a) for n,(a,b) in firsts)
    # special case for first entry, which wants last index of first letter
    kfirst,lfirst = next(regrouped)
    firstitem = (tuple(lfirst)[-1],) if kfirst != 'X' else ()
    #return first item, and first index for all other letters
    return itertools.chain(firstitem,(next(l) for k,l in regrouped if k != 'X'))
Improve this answer

Comments

0 
letters=['A','A','A','A','A','A','A','A','A','A','A','A','B','C','C','X','D','X','B','B','A','A','A','A']
    #     0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23 
prev = letters[0]
result = []
for i in range(len(letters)):
    if prev!=letters[i]:
        result.append((i-1,prev))
    if letters[i]!='X':
        prev = letters[i]
    else:
        prev = letters[i+1]

result.append((len(letters)-1,letters[-1]))
print result

RESULTS IN: (Not OP's desired results, sorry I must have misunderstood. see JSutton's ans)

[(11,'A'), (12,'B'), (14,'C'), (16,'D'), (19,'B'), (23,'A')]

which is actually the index of the last instance of a letter before they change or the list ends.

Improve this answer

4 Comments

sorry, i prefer not to import modules that i don't already have, so this was the first solution that came to mind.
First of all, I'd like to see your timing code; secondly writing code which is easy to understand is substantially more important than a 2x speedup unless you're doing huge processing.
I'm sorry, but not using existing libraries as a reason to write more code is a terrible idea.
I also find my code easier to understand, though i understand its based on individual preference and knowledge.
0

With an aid of dictionary to keep running time linear in number of input, here is a solution:

letters=['A','A','A','A','A','A','A','A','A','A','A','A','B','C','C','X','D','X','B','B','A','A','A','A']

def f(letters):
    result = []
    added = {}
    for i in range(len(letters)):
        if (i+1 == len(letters)):            
            break            
        if letters[i+1]!='X' and letters[i+1]!=letters[i]:
            if(i not in added and letters[i]!='X'):
                result.append((i, letters[i]))
                added[i] = letters[i]
            if(i+1 not in added):
                result.append((i+1, letters[i+1]))
                added[i+1] = letters[i+1]
    return result

Basically, my the solution always tries to add both indices where a change occurred. But the dictionary (which has constant time lookup tells us if we already added the element or not to exclude duplicates). This takes care of adding the first element. Otherwise you can use an if statement to indicate first round which will only run once. However, I argue that this solution has same running time. As long as you do not check if you added the element by looking up the list itself (since this is linear time lookup at worst), this will result in O(n^2) time which is bad!

Improve this answer

3 Comments

This prints: [(11, 'A'), (12, 'B'), (13, 'C'), (16, 'D'), (18, 'B'), (19, 'B'), (20, 'A')]... (19, 'B') is redundant?
this doesn't make sense though, you need 19 B don't you?
also you need (18, B) since it is switch from D to A if you are ignoring X
-1

Here's my suggestion. It has three steps.

  1. Fist, find all the starting indexes for each run of letters.
  2. Replace the index in the first non-X run with the index of the end of its run, which will be one less than the start of the following run.
  3. Filter out all X runs.

The code:

def letter_runs(letters):
    prev = None
    results = []

    for index, letter in enumerate(letters):
        if letter != prev:
            prev = letter
            results.append((index, letter))

    if results[0][1] != "X":
        results[0] = (results[1][0]-1, results[0][1])
    else: # if first run is "X" second must be something else!
        results[1] = (results[2][0]-1, results[1][1])

    return [(index, letter) for index, letter in results if letter != "X"]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.