# Create pairs of items with similarity constraints

I want to create N unordered pairs of items (no repeat pairs, no pairs with repeated items), where each item is only used twice. For example, given the minimal amount of integers greater than 0, one possible set of 4 items would be:

[(0, 1), (0, 2), (3, 1), (3, 2)]


Another valid example would be:

[(0, 1), (1, 2), (2, 3), (3, 0)]


This would be invalid due to repeated pair:

[(0, 1), (0, 1), (2, 3), (3, 1)]


This would be invalid due to the item 0 being used three times:

[(0, 1), (0, 2), (0, 3), (3, 2)]


Also, to be clear the pair (0, 0) is invalid because it is a pair with a repeated item.

My current code for accomplishing this is clumsy and only works multiples of 4. For now, let's assume the code only needs to work for multiples of 4. How could I do this with a better iterator?

num_set = range(4)
res = []
for n1, n2, n3, n4 in zip(num_set[::4], num_set[3::4], num_set[1::4], num_set[2::4]):
res.append((n1, n3))
res.append((n1, n4))
res.append((n2, n3))
res.append((n2, n4))

print(res)


I feel like I should be able to use itertools.combinations(range(4), 2) and some filtering to accomplish this, but I'm not sure how.

• There's a general principle here that you need to discover on your own. Write down all the elements, and draw lines between ones that are part of unordered pairs. What kind of structure results? Can you do it without crossing any lines? – Snowbody Dec 8 '17 at 2:29
• @Snowbody indeed that's the approach I ended up taking in my final answer – Seanny123 Jul 22 '18 at 0:27

The simplest answer I could come up with exploits the structure of the problem and gives a deterministic answer, but since I didn't specify the answer had to be random, I think it's valid.

Basically, the pairs [(0, 1), (1, 2), (2, 3), (3, 0)] are equivalent to some creative slicing of the list d_list = [0, 0, 1, 1, 2, 2, 3, 3]. I couldn't figure out how to slice it properly, so instead I used a hacky re-arrangement of d_list.append(d_list.pop(0)). This gives d_list = [0, 1, 1, 2, 2, 3, 3, 0] which I can then slice into pairs trivially.

Complete code below:

n_items = 5

nums = list(range(n_items))

d_list = []
for nn in nums:
d_list.append(nn)
d_list.append(nn)

d_list.append(d_list.pop(0))

pairs = []
for i1, i2 in zip(d_list[::2], d_list[1::2]):
pairs.append((i1, i2))


It's definitely not the prettiest code, but it works.

Ok, so because I'm primarily a python 2.7 person, I'm not gonna write any real code. Instead, I'll talk through an algorithm, using pseudocode valid in python 2.7 AND python 3.x

We have the list [0,1,2,3,4,5...n-2,n-1,n] to begin with.

Select (0,1)
Select (0,2)
Select (1,3)
Select (2,4)
Select (3,5)
...
Select (n-2,n)
Select (n-1,n)


There's a valid set. Specifically, for any set made of range(n,m):

select (n,n+1)
i = 0
While i+2<m:
select (n+i,n+i+2)
i++
select (m-2,m)
select (m-1,m)


Now I know Select isn't a valid bit of code, but the base algorithm is the same. Furthermore, because this works on any range, it's more robust than your code.

Ok, fine. I'll add some code. No telling if it'll work for 3.x, though.

def Select(lst,index1,index2):
return (lst[index1],lst[index2])
def select_unordered_pairs_from_list(lts):
if len(lts) == 2:
return [Select(lts,0,1)]
if len(lts) == 2:
return [Select(lts,a,b) for a,b in [(0,1),(0,2),(1,2)]]
out = []
out.append(Select(lts,0,1))
i = 0
while i+2<len(lts):
out.append(Select(lts,i,i+2))
i+= 1
j = len(lts)
out.append(Select(lts,j-2,j-1))
return out

• Pretty sure lines 4 and 6 are not supposed to be the same. Maybe line 6 is supposed to be 3? – Snowbody Dec 8 '17 at 2:30

I figured out how to do this with a ton of set math and generalised it to N acceptable repetitions of each items. Here is the code below with a ton of print statements to help understanding and what I consider to be an acceptable amount of code duplication.

import numpy as np
import random

n_items = 6
pick_lim = 2

nums = list(range(n_items-1))
indices = set(range(len(nums)))

picked = list(np.zeros(len(nums), dtype=int))
picked_lim = set()
picked_pairs = {n: set() for n in range(len(nums))}
res = []

for n in range(n_items):
a_pick = indices - picked_lim
print(f"pick from {a_pick}")
if len(a_pick) == 0:
break
a_idx = random.sample(a_pick, 1)[0]

picked[a_idx] += 1
if picked[a_idx] == pick_lim:
print(f"a {a_idx} was picked twice!")
print(picked_lim)

b_pick = indices - {a_idx} - picked_lim - picked_pairs[a_idx]
if len(b_pick) == 0:
break
print(f"pick from {b_pick}")
b_idx = random.sample(b_pick, 1)[0]

picked[b_idx] += 1
if picked[b_idx] == pick_lim:
print(f"b {b_idx} was picked twice!")
print(picked_lim)


• I think you're missing an import statement -- where is np defined? – Snowbody Jul 23 '18 at 20:52