Minimum number of common elements in sets

  • Context: Undergrad 
  • Thread starter Thread starter kamarala
  • Start date Start date
  • Tags Tags
    Elements Minimum Sets
Click For Summary
SUMMARY

The discussion centers on optimizing the selection of items for 500 gift boxes, each containing 40 items, to minimize the number of common items between any two boxes. The user seeks to determine the minimum number of common items and requests an algorithmic approach to achieve this. With 500 unique items available in unlimited quantities, the goal is to ensure that each box remains distinct from others. The conversation highlights the need for a systematic method to calculate item distribution effectively.

PREREQUISITES
  • Understanding of combinatorial optimization
  • Familiarity with PHP programming for algorithm implementation
  • Knowledge of set theory and its applications
  • Basic grasp of algorithm complexity analysis
NEXT STEPS
  • Research combinatorial algorithms for set partitioning
  • Learn about the PHP implementation of the Knapsack problem
  • Explore techniques for minimizing overlap in set selections
  • Investigate the use of randomization in item selection algorithms
USEFUL FOR

This discussion is beneficial for algorithm developers, PHP programmers, and anyone involved in combinatorial optimization or gift box assembly projects aiming for diversity in selections.

kamarala
Messages
2
Reaction score
0
Hello,

Let's say I have 500 boxes and 500 hundred non-identical items.

I would like to have sets of 40, chosen among those 500 hundred items and my objective is to keep the number of same items in any 2 boxes at a minimum.

1. What would be that minimum number of common items?

2. If it's not easy to calculate, could someone suggest an algorithm. I can write little php, so I may try to get it calculated.

Thanks in advance.

p.s. I'm asking it here, hoping that someone smarter than me could come up with a quick way to calculate it. Of course, I'm not expecting anyone to spend much time on it to solve it for me, but it would nice to know if there are no short-cuts to calculate it.
 
Physics news on Phys.org
So some of the 500 items are identical, but not all of them? How many of each identical set are there?
 
nonvestigial said:
So some of the 500 items are identical, but not all of them? How many of each identical set are there?

Hmm, I think I was not clear enough, my bad.

I have unlimited quantity of each item. I would like to fill in the boxes with 40 items and I would like to keep the number of common items in any box to a minimum.

Like, I have 500 different gifts (with unlimited quantity) to choose from and I would like to prepare gift boxes for children and I will put 40 gifts in each of them. I want to keep the boxes that any 2 children gets as different as possible.

I hope I could make it clear.

Edit: And there are a total of 500 boxes / children.
 
Last edited:

Similar threads

Graduate What is the Probability of Sampling a Set with a Certain Size?
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Formalizing infinity sets
  • · Replies 3 ·
Replies
3
Views
448
Undergrad Add an exponential number of elements, what will be the final cardinality?
  • · Replies 16 ·
Replies
16
Views
2K
Undergrad Probability to get a certain number or less by throwing two 6-faced die
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Fair distribution, minimizing envy
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How to measure the 'agreement' between two assays?
  • · Replies 39 ·
2
Replies
39
Views
5K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
Undergrad Map possible values of a set with a condition to the naturals
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Why can sets contain duplicate elements?
  • · Replies 20 ·
Replies
20
Views
4K
Undergrad Countably Infinite Unions and the Real Numbers: Can They Really Be Uncountable?
  • · Replies 4 ·
Replies
4
Views
3K