Dividing a list of numbers in two groups such that numbers in one group don't have any factor common with the numbers in the other group

Question

I have to divide a list of numbers into two groups, such that no number in one group has a factor which is also a factor of any number in the second group. I think we then just need to find out the groups such that the GCD of the product of the numbers in each group is 1. eg-

if we have the list 2,3,4,5,6,7,9 the possible groups would be -

(2,3,4,6,9)(5,7) (2,3,4,5,6,9)(7) (2,3,4,6,7,9)(5)

What I thought of doing initially was -

1. Generate a list of primes up to the max number in the list.
2. Divide all the elements in the list by each prime one by one, and assign 0 to a list if the number is not divisible by the prime, and 1 if it is divisible.
3. Repeat this for all the primes, giving us a matrix of zeroes and ones.
4. Starting from the first prime, put all the elements which have a 1 into one group.
5. If two groups have the same element, join the groups making one single group.
6. Calculate the number of possible ways in which these groups can be combined, and we are done.

From the previous example, the algorithm would look like this -

1. List of primes = [2,3,5,7]
2. After division, the matrix would look like this-

3. Groups=(2,4,6),(3,6,9),(5),(7)
4. Joined groups=(2,3,4,6,9),(5),(7)
5. Finally, the joining is the easy part since I only need the number of ways these can be combined.

I think this algorithm works but is a very bad way of approaching this problem. I can hard-code the primes till a large number and then find the prime closest to my max number, which might make it faster, but still it involves too many divisions if the number of elements is of the order let's say 10E6 or more. I was thinking there was maybe a much better way of approaching this problem. Maybe some mathematical formula that I am missing, or some small logic that can reduce the number of iterations.

My question is about the algorithm so pseudo-code would also work, I don't require finished code. However, I am comfortable with Python, Fortran, C, BASH, and Octave so an answer in these languages would also help, but as I said, the language is not the key point here.

And I guess I might be ignorant of a few terms which might make my question better, so any help with rewording is also appreciated.

Answer 1

tl;dr: Use a prime sieve to get a list of primes, use a disjoint set to store and combine groups

Approach

You're on the right track. You can use the Sieve of Erasthones to get a list of prime numbers, and you only need ~O(n log n) time and memory for prime factoring, which isn't that bad.

Let's reframe the second half of the problem a little bit:

• each number in your original list is a node in a graph
• there is an edge between two nodes if the numbers share a common factor

Now your problem is to find two disjoint groups of nodes. Store these groups in a disjoint set.

Example

A slightly shorter version of your example, with elements [2,3,4,5,6]. Let's keep track of each group of nodes in the subsets column, and iterate through the array above.

| iteration | subsets         | subset1 | description                                                                                                             |
|-----------|-----------------|---------|-------------------------------------------------------------------------------------------------------------------------|
| start     | []              | n/a     |                                                                                                                         |
| 1         | []              | {2}     | add a new subset, 2                                                                                                     |
| 2         | [{2}]           | {3}     | 3 shares no common factors with 2, so create a new subset 2                                                             |
| 3         | [{2},{3}]       | {4}     | 4 shares a common factor with 2, but not with 3, so merge it with {2}                                                   |
| 4         | [{2,4},{3}]     | {5}     | 5 shares no common factors with 2,3 or 4, so create a new subset                                                        |
| 5         | [{2,4},{3},{5}] | {6}     | 6 shares a common factor with {2,4}, so merge it into that.  it also shares a common factor with {3}, so merge that too |
| 6         | [{2,4,3,6},{5}] |         | done                                                                                                                    |   

Method

start with a disjoint set with the standard properties make_set, union and find methods as described on Wikipedia.

1. augment it with get_prime_factors that returns a Python set of prime factors of the elements of that subset for space efficiency, only the parent node should contain this property

def get_prime_factors(x):
    return Find(x)._prime_factors

2. modify union to return a reference to the newly created set and to keep track of the prime factors (set intersection)

def union(x, y):
    # use Wikpidia's code
    # ...

    # add this:
    xRoot._prime_factors |= yRoot._prime_factors
    return xRoot

3. define get_subsets(), a way of iterating over the subsets. the naive way is to iterate over the original array and run find on each. the less naive way is to keep track of parents with another set, but this choice doesn't affect the worst-case runtime.

Code

disjoint_set = AugmentedDisjointSet([])
elems = [2,3,6,5,4]

for new_number in elems:
    subset1 = disjoint_set.make_set(new_number)

    for subset2 in disjoint_set.get_subsets():
        if (subset1.get_prime_factors() & subset2.get_prime_factors()): # merge if the subsets share a common factor
            subset1 = disjoint_set.union(subset1, subset2)

# show result. this may give between 1 (all numbers share a common factor) 
# and infinite subsets (all numbers are relatively prime)
# for your example, this will return something like {2,3,4,6,9}, {5}, {7}
# you can group them however you'd like to.
print('result': disjoint_set.get_subsets())  

Analysis

Worst case runs in O(n^2*a(n)) time, where a(n) is the inverse Ackerman function (i.e. very small), if every element is relatively prime, and O(n) space.

Answer 2

This is a very lengthy way of doing it... You may also run into issues with repeats in the answer if the numbers swap around.

from functools import reduce
from itertools import combinations, chain
import copy

def factors(n):    
    return [x for x in set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) if x != 1]

#this creates a dictionary with the factors as keys and every element of the value list that it is a factor of
#{'2': [2, 4, 6], '3': [3, 6, 9], '4': [4], '5': [5], '6': [6], '7': [7], '9': [9]}
def create_factor_dict(values):
    factor_dict = {}
    for val in values:
        if len(factors(val)) != 0:
            for fac in factors(val):
                if str(fac) in list(factor_dict.keys()):
                    factor_dict[str(fac)] = factor_dict[str(fac)] + [val]
                else:
                    factor_dict[str(fac)] = [val]

    return factor_dict

#this deletes all the factor keys that appear as factor values of another key
#{'2': [2, 4, 6], '3': [3, 6, 9], '4': [4], '5': [5], '6': [6], '7': [7], '9': [9]} --> {'2': [2, 4, 6], '3': [3, 6, 9], '5': [5], '7': [7]}
def delete_duplicates(a_dict):
    for key in list(a_dict.keys()):
        check = copy.deepcopy(a_dict)
        del check[key]
        if int(key) in list(chain.from_iterable(list(check.values()))):
            del a_dict[key]
    return a_dict

#this merges values into groups if they contain common values
#{'2': [2, 4, 6], '3': [3, 6, 9], '5': [5], '7': [7]} -- > [[7], [5], [2, 3, 4, 6, 9]]
def merge_groups(a_dict):
    a_dict = delete_duplicates(a_dict)
    for key in a_dict:
        values = a_dict[key]
        for key2 in [x for x in list(a_dict.keys()) if x != key]:
            if True in [True for x in values if x in a_dict[key2]]:
                a_dict[key] = list(set(a_dict[key] + a_dict[key2]))
    groups = [list(i) for i in set(map(tuple, list(a_dict.values())))]
    return groups

#creates all pairs of 2 then merges into one group
#[[7], [5], [2, 3, 4, 6, 9]] ---> [[7, 5], [7, 2, 3, 4, 6, 9], [5, 2, 3, 4, 6, 9]]
def create_groups(a_dict):
    groups = merge_groups(a_dict)
    groups = [list(chain.from_iterable(x)) for x in list(combinations(groups, 2))]
    return groups




values = [2, 3, 4, 5, 6, 7, 8, 9]               
groups = create_groups(create_factor_dict(values))

#this finds the elements of value that do not appear in each group (that's the complimentary pair)
pairs = []
for x in groups:
    pair = []
    for v in values:
        if v in x:
            pass
        else:
            pair.append(v)
    pairs.append((x, pair))
print(pairs)

it outputs:

[([7, 5], [2, 3, 4, 6, 8, 9]), ([7, 2, 3, 4, 6, 8, 9], [5]), ([5, 2, 3, 4, 6, 8, 9], [7])]