Algorithm practice

Problem:

A bunch of kids from Algo Elementary School are going to a picnic. Kids are to be paired up, and they must be paired up with a friend.
Given n = number of kids, m = number of friend relations, and m number of pairings, compute the number of possible arrangements.
Assume n is even

Example 1:

n = 2 // two kids
m = 1 // 1 friend relation
(0, 1) // kid 0 and kid 1 are friends

Output: 1

Example 2:

n = 4 // four kids
m = 6 // 6 friend relations
(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3)

Output: 3

(0, 1), (2, 3)
(2, 3), (0, 2)
(2, 1), (3, 0)
Solution and outputs:
In [61]:
n = 4
ARE_FRIENDS = {
    0 : [1,2],
    1 : [2,3],
    2 : [3],
    3 : [0]
}
kids = range(0, n)
taken = set()

def areFriends(a, b):
    return ((a in ARE_FRIENDS) and (b in ARE_FRIENDS[a])) or ((b in ARE_FRIENDS) and (a in ARE_FRIENDS[b]))

def pick(k):
    res = 0
    if k >= n-1: # Base case: we are at the last kid, he is either already paired up or there exists no pairing for him
        print ""
        return 1 if len(taken) == len(kids) else 0 # If everyone is paired up, then we have found one good arrangement
    if(k in taken): # Current kid has already been paired up. Moving on...
        return pick(k+1) 

    # Pair up a kid with a buddy, count the number of possible arrangements given this initial pairing.
    for b in range(k+1, n):
        if areFriends(k, b) and (k not in taken) and (b not in taken):
            print "(%s, %s)" % (k, b),
            taken.add(k); taken.add(b)
            res += pick(k+1)
            taken.remove(k); taken.remove(b)
    
    return res


print "Total = %s" % pick(0)
(0, 1) (2, 3) 
(0, 2) (1, 3) 
(0, 3) (1, 2) 
Total = 3
In [62]:
n = 6
m = 10
taken = set()
kids = range(0, n)
ARE_FRIENDS = {
    0 : [1, 2],
    1 : [2, 3, 4],
    2 : [3, 4],
    3 : [4, 5],
    4 : [5]
}
print "Total = %s" % pick(0)
(0, 1) (2, 3) (4, 5) 
(2, 4) (3, 5) 
(0, 2) (1, 3) (4, 5) 
(1, 4) (3, 5) 
Total = 4
In [63]:
n = 2
m = 1
kids = range(0,n)
ARE_FRIENDS = {
    0 : [1]
}
print "Total = %s" % pick(0)
(0, 1) 
Total = 1
In [ ]:
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s