0
$\begingroup$

suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t

  • each number should be in one pair and also every number should be paired

  • a pair(like 0-1) should be present in only one of the pairing. and also every possible pair should be present somewhere

i) 0-1 , 2-3 ,4-5

ii) 0-4 , 1-2 ,3-5

iii) 0-3 , 1-4 ,2-5

iv) 0-2 , 1-5 ,3-4

v) 0-5 , 1-3 ,2-4

similarly if I have N numbers. I need $(N-1)$ pairing of numbers s.t in each pairing there are $N/2$ pairs.

essentially this is grouping $\binom{n}{2}$ combinations into $n-1$ groups s.t each number is present exactly once in each group

$\endgroup$
  • $\begingroup$ Does this problem have a single answer? E.g. your first set is [(0, 1), (2, 3), (4, 5)], though you could just as well start with [(0, 1), (2, 4), (3, 5)] or [(0, 1), (2, 5), (3, 4)]. Depending on your first choice, the other choices are restricted. Does that matter? $\endgroup$ – oerpli Sep 24 at 6:06
  • $\begingroup$ @oerpli order doesn't matter $\endgroup$ – viru Sep 24 at 6:07
  • $\begingroup$ This is not just a question of order. There are multiple solutions, i.e. the sets from my previous comment are all valid but cannot occur in the same solution. See my answer below $\endgroup$ – oerpli Sep 24 at 6:15
1
$\begingroup$

As pointed out by @Pseudonym, this problem is identical to finding a round robin tournament schedule. A straightforward implementation would be the following:

def get_sets(a: list):
    # Simple implementation of
    # https://nrich.maths.org/1443
    center, *rest = a
    for _ in range(len(rest)):
        rest = rest[1:] + rest[:1] # put 1st element to back of list
        solution = [[center, rest[len(rest) // 2]]] # combine middle element with center
        for i in range(len(rest) // 2):
            solution.append([rest[i], rest[~i]]) # combine i-th element from front with i-th from back
        yield solution

for s in get_sets(list(range(50))):
    print(s)

Note that this implementation creates a new list for each "set" in the output. This is not strictly necessary, as the same result could be achieved by using only the initial list (actually array) and use smart indexing.

$\endgroup$
  • $\begingroup$ This is exactly what I was looking for.Thanks, you came up with the solution and also coded it! in such a less time.+1 cause I can't upvote $\endgroup$ – viru Sep 24 at 6:23
  • $\begingroup$ is there more efficient algorithm for this.I want to be for 30 $\endgroup$ – viru Sep 24 at 8:13
  • $\begingroup$ Oh, yes, it can be done in O(k) (k = length of output) time. I will update my answer. $\endgroup$ – oerpli Sep 24 at 17:57
1
$\begingroup$

Your problem is related to the balanced tournament design problem.

Suppose that you have $2n$ tennis players, there are $n$ tennis courts, and you need to play a round robin tournament in $2n-1$ rounds. The courts aren't the same, to to balance the effect of the different courts, you want to ensure that no player competes more than twice on any one court. The problem is to design the rounds.

Formally, a BTD of order $n$ is an arrangement of all of the distinct (unordered) pairs of a set $V$ (where $|V| = 2n$) into a $n$ by $2n-1$ array such that:

  • Every element of $V$ appears precisely once in each column.
  • Every element of $V$ appears at most twice in each row.

While your problem isn't exactly the same as the BTD problem, any solution to the BTD problem is a solution to your problem. So a solution to the BTD problem solves your problem if $N$ is even. (I don't know what you want to do if $N$ is odd.)

The BTD problem has a very simple solution. See, for example, this blog post by Rachel Silverman.

$\endgroup$

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.