CODEWITHSUNDEEP
pythonsetintersectionrebuildpreserve
Herberth
Herberth

Reputation: 13

rebuilding sets and intersection in python

I have the following problem, initially I have 3 sets:

A [1,2,3],B [2,3,4,5] and C [2,5,6,7]

I next consider the intersection of sets two by two and the intersection of all of them

AB [2,3],
AC [2],
BC [2,5] and
ABC [2] (Full intersection)

Now what I want is a new reordering of my sets with the following conditions: 1. preserve the cardinality of each set. 2. preserve the cardinality of all possible intersections.

for example I should get

A [3,4,7],
B [1,3,7,5] and
C [2,6,5,7]

Notice that the new intersection of A and B (now [3,7]) has 2 elements as in the previous intersection, analogously with intersections AC ,BC and full intersection ABC and of course, the cardinality of A, B and C continue to be 3, 4 and 4 respectively. Finally I need to do that process of reorganizing as many times as possible, which I understand depends on the cardinality of the sets and the total number of sets.

Upvotes: 1

Views: 239

Answers (2)

tzaman
tzaman

Reputation: 47770

You could just generate all possible permutations of your original set of elements, and use them as "mappings" from the original elements to a new configuration. So for example, 2345671 maps each number to the next and wraps around; this creates the sets:

A = {2, 3, 4}    # from {1, 2, 3}
B = {3, 4, 5, 6} # from {2, 3, 4, 5}
C = {3, 6, 7, 1} # from {2, 5, 6, 7}

This is pretty straightforward to do using itertools:

from itertools import permutations

def all_configurations(*sets):
    elements = list(set.union(*sets))
    for perm in permutations(elements):
        map = {old: new for old, new in zip(elements, perm)}
        new_sets = [{map[k] for k in old_set} for old_set in sets]
        yield new_sets


A = {1, 2, 3}
B = {2, 3, 4, 5}
C = {2, 5, 6, 7} 

confs = all_configurations(A, B, C)
for conf in confs:
    print(conf)
    # Or: Ax, Bx, Cx = conf

Note how I used a yield statement, this will generate each new permutation one at a time instead of creating them all at once, so you can use this for larger numbers of elements without blowing up your memory. Also, the function as written will work for any number of input sets.

Of course, this will definitely generate some duplicates (e.g. in your example, mapping 6 to 7 and 7 to 6 doesn't change anything) but it should also certainly generate every valid option. Some sample outputs:

[{2, 4, 6}, {3, 4, 5, 6}, {1, 3, 6, 7}]
[{4, 5, 7}, {1, 3, 4, 7}, {2, 3, 6, 7}]
[{3, 5, 6}, {1, 3, 5, 7}, {2, 3, 4, 7}]
[{1, 6, 7}, {1, 2, 4, 7}, {2, 3, 5, 7}]

EDIT: In order to get a fixed number of non-duplicate arrangements, you can change the original code to return a tuple of frozensets instead of a list of sets, that way the whole thing can hashed so you only get uniques. You can then just add things to the output set until it reaches your desired cardinality:

from itertools import permutations

def all_configurations(*sets):
    elements = list(set.union(*sets))
    for perm in permutations(elements):
        map = {old: new for old, new in zip(elements, perm)}
        new_sets = tuple(frozenset(map[k] for k in old_set) for old_set in sets)
        yield new_sets

def n_configurations(n, *sets):
    output = set()
    confs = all_configurations(*sets)
    for conf in confs:
        output.add(conf)
        if len(output) >= n:
            break
    return output


A = {1, 2, 3}
B = {2, 3, 4, 5}
C = {2, 5, 6, 7} 

confs = n_configurations(10, A, B, C)
for a, b, c in confs:
    print(a, b, c)

This produces the following 10 configurations:

(frozenset([1, 2, 3]), frozenset([2, 3, 5, 6]), frozenset([2, 4, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 6]), frozenset([2, 5, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 6, 7]), frozenset([2, 4, 5, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 6]), frozenset([2, 4, 5, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 5]), frozenset([2, 4, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 5, 6]), frozenset([2, 4, 5, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 7]), frozenset([2, 5, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 5]), frozenset([2, 5, 6, 7]))
(frozenset([1, 2, 3]), frozenset([2, 3, 4, 7]), frozenset([2, 4, 5, 6]))
(frozenset([1, 2, 3]), frozenset([2, 3, 5, 7]), frozenset([2, 4, 6, 7]))

Upvotes: 0

mushishi
mushishi

Reputation: 151

Can this get you started?

    import random
    import itertools


    def same_intersect_len(x, y, z):
        return (len(x & y) == len(a & b) and
                len(x & z) == len(a & c) and
                len(z & y) == len(b & c) and
                len(x & y & z) == len(a & b & c))


    a = set(random.sample(range(0, 10), 1))
    b = set(random.sample(range(0, 10), 2))
    c = set(random.sample(range(0, 10), 3))

    elements = list(a) + list(b) + list(c)

    ps = set(itertools.permutations(elements))
    new_a = list()
    new_b = list()
    new_c = list()
    for p in ps:
        candidate_a = {p[len(a) - 1]} - a
        candidate_b = set(p[len(a):len(a) + len(b) - 1]) - b
        candidate_c = set(p[len(a) + len(b):len(a) + len(b) + len(c) - 1]) - c
        if same_intersect_len(
                candidate_a,
                candidate_b,
                candidate_c):
            new_a.append(candidate_a)
            new_b.append(candidate_b)
            new_c.append(candidate_c)

Upvotes: 0

Related Questions