algorithm to find max group of pairs of a set. But every object in the set can be used max 3 times, and a pair can be used more than once

Question

Explanation

I need to find an algorithm to find all pairs of a set. Every object in the set can be used maximum 3 times, and a pair can be used more than once.

for example: ['a','b','c'] the pairs will be → 'ab','ac','bc', 'ab'. I tried to use all the pairs and then to filter them, but it won't work because the pairs can be used more than once

Code

def fn_pair(start, rest, n):
    if n == 0:
        final_list.append(start)
    else:
        for i in range(len(rest)):
            fn_pair(start + rest[i], rest[i+1:], n-1)

How about using the [round-robin algorithm](https://stackoverflow.com/questions/64604793/get-n-k-unique-sets-of-2-from-list-of-length-n-in-python/64606498#64606498), and going for three rounds? — Stef, May 16 '22 at 09:25

Victor Lee · Answer 1 · 2022-05-17T11:58:52.960

The max group of pairs of a set: int(m * n / 2) or m * n // 2

m is the used max times of one object
n is the length of a set

Had test m from 2 to 4, n from 2 to 9.

In general, about this scenario, here is a simple formula: int(m * n / p), which p is the elements of a pair in here is 2.

Just image that, finding the max groups of pairs of a set in your scenario, the all elements which would be composed the pairs are from the m times of n(the elements of a set), and divide to the groups dependent on the require elements in a group such a pair is 2, to get the whole groups it should be round down(integer part) of the result.

The group list content would be different dependent of the search method.

Here is one of fake code:

1, create a dictionary called d which key is the object and the value is m: like d = {'a': 3, 'b': 3, 'c': 3}
2, create a list for save the pairs, like l
2, start a loop
   remove the value equal to 0 element in d
   if len(d) less than 1, break loop
   if len(d) equal to 1
       - if the element value larger than 1, 
           then generate the pairs as double of key(like 'aa'),
           value subtract 2
           append pairs to l
           continue loop
       - else, break loop
   sorted d by the value from large to small
   generate the pairs from index 0(first key) with others until to the end: like 'ab', 'ac', append to l
   at the same time, the consistent value subtract 1:  d = {'a': 1, 'b': 2, 'c': 2}
   end a loop
3, output the pairs list l

reference sorted dictionary by the value

algorithm to find max group of pairs of a set. But every object in the set can be used max 3 times, and a pair can be used more than once

1 Answers1