2
\$\begingroup\$

I have a list of tuples (key, value1, value2, ...). I simplify the tuple here so it is only of length 2. Keys contain duplicated figures.

xs = zip([1,2,2,3,3,3,4,1,1,2,2], range(11)) # simple to input

[(1, 0),
 (2, 1),
 (2, 2),
 (3, 3),
 (3, 4),
 (3, 5),
 (4, 6),
 (1, 7),
 (1, 8),
 (2, 9),
 (2, 10)]

Now, I would like to build a function, which takes the list as input, and return a list or generator, which is a subset of the original list.

It must captures all items where the keys are changed, and include the first and last items of the list if they are not already there.

f1(xs) = [(1, 0), (2, 1), (3, 3), (4, 6), (1, 7), (2, 9), (2, 10)]
f1([]) = []

The following is my code, it works, but I don't really like it:

xs = zip([1,2,2,3,3,3,4,1,1,2,2], range(11))

def f1(xs):
    if not xs:
        return
    last_a = None # I wish I don't have to use None here.
    is_yield = False
    for a, b in xs:
        if a != last_a:
            last_a = a
            is_yield = True
            yield (a, b)
        else:
            is_yield = False
    if not is_yield:
        yield (a, b) # Ugly...in C# a, b is not defined here.

print list(f1(xs))
print list(f1([]))

What's a better (functional or nonfunctional) way of doing this?

\$\endgroup\$
2
  • \$\begingroup\$ @Barry I rephased a little bit. My input list is a list of tuples... so on input [(1,a),(2,b),(2,c)] I want [(1,a),(2,b),(2,c)] \$\endgroup\$ – colinfang Oct 27 '13 at 23:10
  • 1
    \$\begingroup\$ if you want an answer for specific languages you need to post separate questions with the coding done in those languages. we will not translate this code for you, nor will we write code for you \$\endgroup\$ – Malachi Nov 27 '13 at 16:19
2
\$\begingroup\$

The itertools library has a handy function for this problem called groupby:

def f1(xs):
    for _, group_iter in itertools.groupby(xs, key = lambda pair: pair[0]):
        group = list(group_iter)
        yield group[0]

That'll get us the pairs for which the first element changed from the previous one. Now we just need to make sure we're yield-ing the last element. Which will only NOT be yielded if the last group has size more than 1, hence:

def f1(xs):
    for _, group_iter in itertools.groupby(xs, key = lambda pair: pair[0]):
        group = list(group_iter)
        yield group[0]

    # make sure we yield xs[-1]
    if len(group) > 1:
        yield group[-1]
\$\endgroup\$
2
  • \$\begingroup\$ great, don't know that groupby is not the same as SQL \$\endgroup\$ – colinfang Oct 27 '13 at 23:47
  • 2
    \$\begingroup\$ Need group = None and then check if group to handle empty xs. \$\endgroup\$ – colinfang Oct 28 '13 at 17:35
1
\$\begingroup\$

For interest value here's a custom recursive solution in F# that performs a pairwise comparison, always keeping the first value, and the last if it wasn't already included.

let pairwiseFilter input = 
    let rec aux acc = function
        | x::y::xs when fst x <> fst y -> aux (y::acc) (y::xs)
        | x::y::xs -> aux acc (y::xs)
        | x::[] -> List.rev (if x <> acc.Head then x::acc else acc)
        | [] -> acc
    aux [List.head input] input

Note the requirement to always include the first item is handled by simply passing it in as the initial value of the results accumulator. From there we compare the first and second items, and if they are different we add the second item to the results. Then we take the second item and cons it to the rest of the list (pairwise) which is processed recursively.

Finally the resulting list has the last element appended if it wasn't already in the previous step (eg, its not the same as the head of the results accumulator). The results are then reversed to preserve the original input order.

\$\endgroup\$
1
\$\begingroup\$

Here's a sloution using Seq.pairwise:

let f input = 
    let result = 
        [-1,-1] @ input
        |> Seq.pairwise 
        |> Seq.filter (fun ((key1, valu1), (key2, value2)) -> key1 <> key2)
        |> Seq.map snd
        |> Seq.toList
    if not input.IsEmpty && Seq.last result <> Seq.last input 
    then result @ [Seq.last input] else result 

We add a dummy element to the beginning of the list to make sure it is included, and then at the end cover the last item

>let xs = [1, 0
          2, 1
          2, 2
          3, 3
          3, 4
          3, 5
          4, 6
          1, 7
          1, 8
          2, 9
          2, 10]
>f xs
val it : (int * int) list =
  [(1, 0); (2, 1); (3, 3); (4, 6); (1, 7); (2, 9); (2, 10)]

>f []
val it : (int * int) list = []
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.