Create pairs of items with similarity constraints

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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!")
        picked_lim.add(a_idx)
        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!")
        picked_lim.add(b_idx)
        print(picked_lim)

    picked_pairs[a_idx].add(b_idx)

    res.append((nums[a_idx], nums[b_idx]))
    print(f"{res[-1]}\n")

print(res)

Bonus Internet points for generalizing this algo to triplets.