# 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 :
```n = 4
ARE_FRIENDS = {
0 : [1,2],
1 : [2,3],
2 : ,
3 : 
}
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 :
```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 : 
}
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 :
```n = 2
m = 1
kids = range(0,n)
ARE_FRIENDS = {
0 : 
}
print "Total = %s" % pick(0)
```
```(0, 1)
Total = 1
```
In [ ]:
Advertisements