Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have 2N items and I need to form 2N sets each with N items. The items should be evenly distributed. I don't know how to define this rigorously, but the number of common elements among any two sets should be minimized and equal to at most the average value. Also, each item appears in N and exactly N sets.

For example, when N=2, valid sets can be (1,2),(1,3),(2,4),(3,4)


It is difficult to write down for N=4, but I'll try to: (1,2,3,4),(1,2,5,6),(1,3,7,8),...

--- edit --- [Feel free to reword and/or remove this. DL]

The result should be 2n subsets of {1,2,...,2n}, with each subset having n elements.

Requirement 1: Each of the elements 1,2,...,2n exactly twice (probably this needs to be exactly n times, to get the numbers to work out).

Requirement 2: Minimize the maximal intersection size of any two subsets, subject to requirement 1.

--- end edit ---

share|improve this question

closed as unclear what you're asking by Kuba, m_goldberg, belisarius, Sjoerd C. de Vries, bobthechemist Apr 9 at 17:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

Could you give a few more examples? I'm not sure that I understand. –  Mr.Wizard Jan 6 at 21:55
Also, please compare this question: mathematica.stackexchange.com/q/3044/121 –  Mr.Wizard Jan 6 at 21:57
I do not understand why {1,2,3,4} gives {1,2},{1,3},{2,3},{3,4} based on what? but it kind of is such that the common number of elements in any two sets are minimized and equal to at most a common value I am struggling also to understand what this means. but may be you can look at Subsets and see if it does sort of what you want. –  Nasser Jan 7 at 0:09
In your first example the third pair, (2,3), should instead be (2,4). Your bigger example is strangely incomplete. That makes it very difficult for readers to understand what exactly you are requesting. –  Daniel Lichtblau Jan 7 at 3:41
There are more than one answer to this. What about (1,2),(2,3),(3,4),(1,4) –  Nasser Jan 7 at 8:06

1 Answer 1

I understood the question to be: generate a collection $C = \{s_i\}$ with $2n$ elements where each $s_i$ is a subset of length $n$ of $D_n = \{1,\ldots, 2n\}$ such that each $x \in D_n$ appears in exactly $n$ of the $s_i$.

sets[n_] := Module[
  {per, set, k},

  per = RandomSample[Range[1, 2 n]];
  set = Table[RotateLeft[per, k], {k, 0, n - 1}];

  Sort /@ Transpose[set] // Sort

For example,

In[1]:= sets[4]

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

The solution notes that the subsets are the transpose of $n$ distinct permutations that pairwise do not have a fixed point. This algorithm does not produce all solutions. That requires producing permutations that pairwise have no fixed point and eliminating spurious symmetries.

share|improve this answer
There is no one solution to this. For example sets[3] gives {{1, 2, 3}, {1, 2, 4}, {1, 4, 6}, {2, 3, 5}, {3, 5, 6}, {4, 5, 6}} but what is wrong with {123},{234},{345},{456},{561},{612} ? –  Nasser Jan 7 at 9:58
There is nothing wrong with it the way I read it. The function sets[n] generates a new random solution of size $n$ every time it is run. It just doesn't generate all of them even if run many times. –  Hbar Jan 7 at 13:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.