1

I have a list of elements. I want to know if there are two pairs of elements in the list, in which the elements of the pair have the same value.

My idea is that I first compare all the elements in the list, if a pair is found, remove the pair from the list, then proceed again. Thus I think I can use recursion to do this task, but limit the depth to 2 to solve the problem.

Here is my first try:

    recursion_depth=0
        def is_twopair(card):
            nonlocal recursion_depth
            if recursion_depth==2: return True
            for i in range(0, len(card)):
                for k in range(i+1,len(card)):
                    if card[i].value==card[k].value:
                        del card[k], card[i]
                        recursion_depth+=1
                        is_twopair(card)      
                    else: continue
                else: continue
            else: return False

I use the variable recursion_depth to record the the depth of recursion, but then realize that the return command doesn't immediately terminate the function and return true, but returns to its original caller is_twopair(card) instead. So my question is:

  1. Is there a way to immediately terminate the function and return the result true?
  2. Is there a way to limit the depth of recursion?

I know there maybe several ways to work around this. But I want to stay faithful to my idea and use this as an opportunity for learning.

Improve this question
2
  • 1
    Can you copy an example of your list? Commented Feb 16, 2017 at 20:02
  • My list is a list of objects of class card, which model cards in poker. So for example: [TD, TH, KD, KH, QD]. ( TD means ten diamond, TD means ten heart, KD means King Diamond etc). The attribute value indicates one of the 13 possible values of card(2,3,4...10, J, Q,K A). But I don't think it's quite relevant to the question. The problem can be casted in any lists of any types. The above list should return true ( we have 2 tens cards, 2 king cards) Commented Feb 16, 2017 at 20:14

3 Answers 3

Reset to default
2

I don't believe you can "break out" of the recursion without some serious black magic, nor do I believe that you should try to. Cascading the return value up the calling chain is typically a fine approach.

I'd personally avoid using a nonlocal variable and keep track of the recursion depth within the scope of each function call.

def remove_pairs(card, count=2, depth=0):
    if depth == count:
        return card

    for i in range(0, len(card)):
        for j in range(i+1, len(card)):
            if card[i].value == card[j].value:
                del card[j], card[i]
                return remove_pairs(card, count, depth+1) # add return here

Moving the tracking of the depth into the function itself will allow the function to be called repeatedly from different locations without issue.

Additionally, the code can be cleaned up some using itertools.combinations.

from itertools import combinations

def remove_pairs(cards, count=2, depth=0):
    if depth == count:
        return cards

    for card1, card2 in combinations(cards, 2):
        if card1.value == card2.value:
            cards.remove(card1)
            cards.remove(card2)
            return remove_pairs(cards, count, depth+1)
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

This is how I track depth, if trying to analyze a performance issue. It's also good to know about sys.setrecursionlimit() but that's more for increasing it if you specifically know you need some finite value slightly bigger than the default (e.g. for some dynamic programming algorithms).
I don't like how you abort the recursion at some arbitrary depth, but return a value anyway. That should be some kind of exception.
@KennyOstrom The question specifically asks for the recursion to be aborted at a depth of 2.
Okay, my bad. I wasn't really clear what OP was trying to do, but this answers the actual question of depth. +1
@KennyOstrom: Maybe I should try to explain my algorithm again to motivate the question. The function takes a list, outputs true if there are two pairs whose 2 elements are the same, false otherwise. I search for such pair, found a pair, remove them from the list, search again with the new list, found the second pair -> output True, other False.
|
0

I think the piece you're missing is a return call to pass on the results of a recursive call back up to the previous caller:

if card[i].value==card[k].value:
    del card[k], card[i]
    recursion_depth+=1
    return is_twopair(card)       # add return here!

I don't really think recursion is a natural way to solve this problem, but with the above change, it should work. You could avoid needing to use a nonlocal variable by passing the depth as an optional parameter.

Improve this answer

1 Comment

I use recursion because I've just learned it and want to apply it in some way. ;)
0 
yourList = [1,1,2,2,3,4]
yourDict = {}
for i in yourList:
    yourDict[i] = yourList.count(i)

This code will return the number of ocurrences for every value in the list so you can determinate the number of pairs..

In this case:

yourDict - - > {1: 2, 2: 2, 3: 1, 4: 1}

The value 1 appear 2 times, the value 2 appear 2 times, the value 3 and 4 appear 1 time.

Improve this answer

2 Comments

I'm not sure that this is what the OP meant. However, here's a much shorter way to do what you did: from collections import Counter count = Counter(yourList)
This is a nice way to do my task. Thanks for the answer ! I want to know if my way is possible though.

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.