**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)
```

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)
```

In [63]:

```
n = 2
m = 1
kids = range(0,n)
ARE_FRIENDS = {
0 : [1]
}
print "Total = %s" % pick(0)
```

In [ ]:

Advertisements