CODEWITHSUNDEEP
pythonmathparallel-processingcombinatoricsdiscrete-mathematics
user1363214
user1363214

Reputation: 301

Generate k most subsets unique pair of elements

I am writing a Cuda application that should calculate a function over two elements of my set S. But the order of the pair doesnt make any difference, so: f(a,b) = f(b,a)

For that reason, I want to generate all subsets of S with max size K, without duplicating pairs of elements between the sets.

In other words, given any two subsets, I don't want the intersection of them to be larger than one element. (This way I can avoid calculating the function of those two elements multiple times)

Example:

Given S={1,2,3,4,5,6,7,8,9} and K=3, the output should be something like this: 

{ {1,2,3}, {1,4,5}, {1,6,7}, {1,8,9}, {2,4,6}, {2,5,7}, {2,8}, {2,7,9}, {3,4,7},
  {3,5,8}, {3,6,9}, {4,5,9} }

But the output should not look like this:

{ {1,2,3}, {1,4,5}, {1,6,7}, {1,8,9}, {2,4,6}, {2,5,7}, {2,6,8}, {2,7,9}, {3,4,7},
  {3,5,8}, {3,6,9}, {4,5,9} }

Because the intersection of {2,4,6} and {2,6,8} is {2,6}.

Upvotes: 4

Views: 576

Answers (3)

jamylak
jamylak

Reputation: 133754

>>> from itertools import combinations, chain
>>> s = {1,2,3,4,5,6,7,8,9}
>>> k = 3
>>> seen = set()
>>> subset_sizes = reversed(range(2,k+1)) # [3,2] for this example. Reversed since you favor the sets with larger values of K
>>> for item in chain.from_iterable(combinations(s,i) for i in subset_sizes):
        pairs = set(combinations(item,2))
        if not pairs.intersection(seen):
            seen.update(pairs)
            print(item)

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

Upvotes: 1

user1349573
user1349573

Reputation: 1

you can do this :

    P := {1, 2, 3, 4, 5, 6}; setpartition(P, 3);
   {{{1, 2, 3}, {4, 5, 6}}, {{1, 2, 4}, {3, 5, 6}}, 

     {{1, 2, 5}, {3, 4, 6}}, {{1, 2, 6}, {3, 4, 5}}, 

     {{1, 3, 4}, {2, 5, 6}}, {{1, 3, 5}, {2, 4, 6}}, 

     {{1, 3, 6}, {2, 4, 5}}, {{1, 4, 5}, {2, 3, 6}}, 

     {{1, 4, 6}, {2, 3, 5}}, {{1, 5, 6}, {2, 3, 4}}}

Upvotes: 0

dfb
dfb

Reputation: 13289

I'm going to post a non-answer in hopes it helps us nail down the question: The question I'm answering below is

Given a set S, generate the maximal cardinality set of all subsets of S such that each subset is less than size K and no two subsets contain an intersection of cardinality > 1

If we fix the size of the subsets (k=3 rather than k<=3) you want, this is easy to do in an non-efficient manner:

  1. Generate all subsets of size k from S
  2. Keep removing things until no intersection is present

Some questions come from this

  1. Is there a more efficient way to do this
  2. Does not fixing k change this solution, is it optimal to always take subsets of a largest size
  3. Is there an optimal set such that we can choose a size t<=k and have all the subsets be of that size

For 2) I think the answer is no:

Observation: For small N, simply generating the pairs is better than generating subsets of size K. Generating a subset of size >2 eliminates only one pair, generating a subset of k eliminates k choose 2 pairs. Choosing size K is only better if 

n/(k choose 2) = k/(k!/(k-2)!2!) = 2n/(k*(k-1)) > (n*n-1)/2 = (n choose 2)
1/(k*(k-1)) > (n-1)/4n

Only for sufficiently large N is this true:

1/(k*(k-1)) > 1/4 
  (k*(k-1)) > 4, k>=3

For 3) I think the answer is yes

The number of subsets is maximized at C(n,k)/C(k,2) , we can calculate this using the formula to find the optimal k. If there are pairs that remain, we can simply add those to the list as if k=2

Upvotes: 0

Related Questions