CODEWITHSUNDEEP
pythonlist-comprehensioncombinationspython-itertoolssampling
Cal P
Cal P

Reputation: 19

Creating samples after sample without duplicates using itertools and list comprehensions

Looking for a more efficient way to achieve a desired result. Combinations is first used to create a list of items taken two at a time:

combos = itertools.combinations(range(1,6),2) b=list(combos)

[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

Starting with the first firsts tuple (1,2), I need to identify which other 2-tuple can be used to create a 4 tuple where the 2nd tuple has no elements in common with the first. (Akin to sampling two players for one team, and two for another).

The desired result is a maximum set of 4 tuples from the list (b) above, where all there are no duplicates. Note For this exercise: (3,4,1,2) is a duplicate of (1,2,3,4). Continuing with the team analogy, it is because the opponents are the same: (1,2) vs. (3,4). Effectively cuts the list in half.

The code below creates the desired output:

x = [(b[i][0], b[i][1], b[j][0], b[j][1])
     for i in range(0,len(b))
     for j in range(i+1,len(b))
     if b[i][0] != b[j][0]
     and b[i][0] != b[j][1]
     and b[i][1] != b[j][0]
     and b[i][1] != b[j][1]]

[(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 2, 4), (1, 3, 2, 5), (1, 3, 4, 5), (1, 4, 2, 3), (1, 4, 2, 5), (1, 4, 3, 5), (1, 5, 2, 3), (1, 5, 2, 4), (1, 5, 3, 4), (2, 3, 4, 5), (2, 4, 3, 5), (2, 5, 3, 4)]

Got the right result Choose(5,2) X Choose (3,2) cut in half for 10 * 3 /2 = 15 4-tuples.

I wanted to get the communities input if there is possibly a better way to generate the list. Clunky, but it works. Cheers and Thanks!

Upvotes: 0

Views: 85

Answers (3)

blhsing
blhsing

Reputation: 106936

Both @kcsquared and @hilberts_drinking_problem's answers hard-codes permutations specifically for 4 selected players, which is hardly ideal if the number of players in a match can vary.

A more generic solution to the problem of any even number of players would be to ensure the uniqueness of the outputting teams by first setting apart a specific player from the players picked for a match and then picking teammates for it. Those that are not its teammates are on the other team, which we can find out by using the set.difference method:

from itertools import combinations

# produces unique matches of m players from a pool of n players
def matches(n, m):
    for first, *rest in combinations(range(1, n + 1), m):
        for teammates in combinations((rest := set(rest)), m // 2 - 1):
            yield first, *teammates, *rest.difference(teammates)

print(*matches(5, 4), sep='\n')

This efficiently outputs:

(1, 2, 3, 4)
(1, 3, 2, 4)
(1, 4, 2, 3)
(1, 2, 3, 5)
(1, 3, 2, 5)
(1, 5, 2, 3)
(1, 2, 4, 5)
(1, 4, 2, 5)
(1, 5, 2, 4)
(1, 3, 4, 5)
(1, 4, 3, 5)
(1, 5, 3, 4)
(2, 3, 4, 5)
(2, 4, 3, 5)
(2, 5, 3, 4)

Upvotes: 1

kcsquared
kcsquared

Reputation: 5409

You can generate these lazily (so minimal memory is needed) and without needing to filter duplicates by iterating over combinations of length 4 instead of pairs of combinations of length 2.

Suppose you have an ordered list of 4 numbers: a < b < c < d. These 4 numbers will be part of exactly 3 results in the answer: a will be first, and we have 3 choices for the second number, after which the last two numbers must go in order.

Then just use itertools.chain() for lazy evaluation:

ans = itertools.chain.from_iterable(
        (((a, b, c, d),
          (a, c, b, d),
          (a, d, b, c))
         for a, b, c, d in itertools.combinations(range(1, 6), 4)))

producing:

(1, 2, 3, 4)
(1, 3, 2, 4)
(1, 4, 2, 3)
(1, 2, 3, 5)
(1, 3, 2, 5)
(1, 5, 2, 3)
(1, 2, 4, 5)
(1, 4, 2, 5)
(1, 5, 2, 4)
(1, 3, 4, 5)
(1, 4, 3, 5)
(1, 5, 3, 4)
(2, 3, 4, 5)
(2, 4, 3, 5)
(2, 5, 3, 4)

Upvotes: 1

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

You can generate all unique 4-tuples and add permutations:

idxs = [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]]
result = list()

for comb in itertools.combinations(range(1, 6), 4):
  for idx in idxs:
    result.append(tuple([comb[i] for i in idx]))

Upvotes: 1

Related Questions