1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Snowbody Dec 8 '17 at 2:29
  • \$\begingroup\$ @Snowbody indeed that's the approach I ended up taking in my final answer \$\endgroup\$ – Seanny123 Jul 22 '18 at 0:27
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Pretty sure lines 4 and 6 are not supposed to be the same. Maybe line 6 is supposed to be 3? \$\endgroup\$ – Snowbody Dec 8 '17 at 2:30
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think you're missing an import statement -- where is np defined? \$\endgroup\$ – Snowbody Jul 23 '18 at 20:52
  • \$\begingroup\$ @Snowbody fixed the missing import. However, I'm quite skeptical this code works 100%. I switched to a different answer later, which makes me think there was problems with this one. \$\endgroup\$ – Seanny123 Jul 23 '18 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.