Register to reply

Algorithm for dividing a set of numbers into groups

by jorgendt
Tags: algorithm, dividing, groups, numbers
Share this thread:
jorgendt
#1
Feb20-12, 03:50 PM
P: 1
I'm looking for an algorithm for dividing a set of numbers into groups, and then doing it again in such a way that no numbers are in a group together more than once.

For instance if you have 18 numbers and divide them into groups of three you should be able to do this 8 times without any numbers having to be in the same group more than once. Any idea how I can do this?

This website: http://mathpages.com/home/kmath388.htm
kinda describes what I'm looking for, but I don't quite get the hang of how they do it, when I try to do something similar with other numbers I end up with repeats (I try to replicate the part where they divide 24 people into four-man-groups in seven different ways).

Thanks in advance for any help. :)
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
jambaugh
#2
Feb20-12, 04:44 PM
Sci Advisor
PF Gold
jambaugh's Avatar
P: 1,776
Firstly it is useful to count how many ways this can be done. There is a function which does this called the multinomial coefficient (generalization of the binomial coefficient).

If you wish to divide a set of N objects into groups of size [itex]n_1, n_2,\cdots , n_k[/itex] where these [itex]n[/itex]'s add up to big N, the number of ways is:
[tex] \frac{N!}{n_1 !\cdot n_2 ! \cdot \ldots \cdot n_k!},\quad \text{where}\quad n!=n(n-1)(n-2)\cdots 1[/tex]
(i.e. 5! = (5)(4)(3)(2)(1) = 120.)

So the number of ways to divide 18 objectsinto 6 specific partitions of 3 each is...
[tex]\frac{18!}{3!\cdot 3! \cdot 3! \cdot 3! \cdot 3! \cdot 3! }=...
\frac{18\cdot 17 \cdot 16 \cdot 15\cdot 14\cdot 13 \cdot 12\cdot 11\cdot 10 \cdot 9 \cdot 8\cdot 7\cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6\cdot 6\cdot 6 \cdot 6\cdot 6\cdot 6}
=\ldots = 137,225,088,000[/tex]
That's if each of the 6 groups of 3 has different meaning. If however you simply want to figure ways to divide them up into sets of a given size you need to divide by the number of ways to rearrange partitions of a given size. In the above example there are 6 sets of size 3 so you divide by 6! (six factorial = 720) to get 190,590,400.

Now counting is good, but if you need an algorithm to enumerate every case then that's tough especially if you want to be sure to get every case but not repeat any equivalent cases. If you simply want to picke one arrangement at random then put all elements in a list, shuffle the list thoroughly and pick the first [itex]n_1[/itex] of that list, the next [itex]n_2[/itex] of that list, ... and so on.
MrAnchovy
#3
Feb20-12, 07:07 PM
P: 511
There is no generalised algorithm as that page (and others on this problem such as this one and this one) hint at.

If you can't use the already-generated solutions on those pages you are going to need to build some method of spanning possible combinations either with brute force or some evaluation/backtracking algorithm.


Register to reply

Related Discussions
Isomorphism between groups of real numbers Linear & Abstract Algebra 3
Dividing/Multiplying Imaginary Numbers General Math 6
Help With Pseudo Coded Algorithm for The Diamond-Square Algorithm Engineering, Comp Sci, & Technology Homework 0
Dividing large numbers General Math 7
196-Algorithm (palindromic numbers) Linear & Abstract Algebra 4