Page 1 of 2
How many possible combinations in a set?
Posted: Sun Apr 05, 2009 3:04 pm
by Mistrel
If I have an array of 9 numbers (1 - 9) what equation can I use to determine how many possible combinations there are in the set? Also, how can I loop through this number and output each possible combination?
Posted: Sun Apr 05, 2009 3:15 pm
by netmaestro
If you assume that permutations do not count, i.e 4,5 and 5,4 don't count as two combinations, then for set N with group size R, this is the formula:
So for example if you had all four queens in a deck of cards, how many pairs of queens do you have? Applying the formula, witn N=4 and R=2:
If by combinations you mean pairs, then plugging 9 and 2 into the equation you get:
Posted: Sun Apr 05, 2009 3:22 pm
by Mistrel
netmaestro wrote:If you assume that permutations do not count, i.e 4,5 and 5,4 don't count as two combinations ..
Each number can occur only once in the set (only once instance of each number 1 - 9). The goal is to find out how many different orders each number can be in. For example:
Code: Select all
1, 2, 3, 4, 5, 6, 7, 8, 9
2, 1, 3, 4, 5, 6, 7, 8, 9
3, 2, 1, 4, 5, 6, 7, 8, 9
4, 2, 3, 1, 5, 6, 7, 8, 9
I'm trying to express this in programming terms. Basically, I have an array of 9 numbers and I want to identify all possible combinations within the array. The total number of possible combinations is important for allocating memory but I want to actually output the different combinations as well.
Posted: Sun Apr 05, 2009 3:25 pm
by netmaestro
Ok I missed the boat then. Let me consider this for a few minutes.
Posted: Sun Apr 05, 2009 3:44 pm
by Mistrel
Thank you for taking the time. My math skills are very rusty.
Posted: Sun Apr 05, 2009 5:21 pm
by Kaeru Gaman
should be 9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 = 362880
first digit has 9 possibilities,
second has 8 (because the first may not be repeated)
third has 7 (because first and second may not be repeated)
etc..
Posted: Sun Apr 05, 2009 9:38 pm
by Little John
> Each number can occur only once in the set (only once instance of each number 1 - 9). The goal is to find out how many different orders each number can be in.
These are not combinations in a set. They are called Permutations.
> should be 9!
Yes, it is.
Generally speaking, when the number is n, then n! is called the Factorial.
Regards, Little John
Posted: Mon Apr 06, 2009 12:45 am
by netmaestro
@Mistrel: Little John is correct about Kaeru Gaman being correct. I've taken the time to write a routine that generates the list, here it is:
Code: Select all
; Find all permutations of a 9-digit number
Declare Shift( Array s(1), start )
Global Dim r(9)
For i=1 To 9
r(i)=i
Next
Global NewList item()
For e=1 To 9
For f=1 To 8
For g=1 To 7
For h=1 To 6
For i=1 To 5
For j=1 To 4
For k=1 To 3
For l=1 To 2
shift(r(),8)
AddElement(item())
item()=r(1)*100000000+r(2)*10000000+r(3)*1000000+r(4)*100000+r(5)*10000+r(6)*1000+r(7)*100+r(8)*10+r(9)
Next
shift(r(),7)
Next
shift(r(),6)
Next
shift(r(),5)
Next
shift(r(),4)
Next
shift(r(),3)
Next
shift(r(),2)
Next
shift(r(),1)
Next
SortList(item(),#PB_Sort_Ascending)
If CreateFile(0, "c:\test.txt")
ForEach item()
WriteStringN(0, Str(item()))
Next
CloseFile(0)
EndIf
Debug ListSize(item())
Procedure Shift( Array s(1), start )
s(0)=s(ArraySize(s()))
For i=ArraySize(s()) To start+1 Step -1
s(i)=s(i-1)
Next
s(start)=s(0)
EndProcedure
I'm sure it could be written better and faster but I failed so many times trying to get it right that I'm not going to mess with it now that it works!
Although it really is quite inefficient as it performs 623529 shifts to generate 362880 unique results. A well-written routine would make 362880 swaps of two elements to create the same list. But at this point I don't care. It runs in 63 milliseconds on my computer, which isn't a particularly fast one.
Posted: Mon Apr 06, 2009 12:41 pm
by einander
May be this helps?
Code: Select all
Procedure Permute(n,Base)
Pw=Pow(Base,n)
Dim A.L(n + Base-1)
Dim a$(Pw)
For i = 1 To Pw
P = 1
For H = n To 1 Step -1
If A(H) < 16 : a$(i) + Hex(A(H))
Else : a$(i) + Chr(A + 55)
EndIf
Next H
Debug Str(Sum)+" "+a$(i)
Sum+1 ; <<<<< number of permutations
If A(P) = Base-1
Repeat
A(P) = 0 : P + 1
Until A(P) < Base-1
EndIf
A(P)+1
Next i
Dim a$(0): Dim A.L(0)
EndProcedure
n=4 ;change your number of digits
Base= 6 ;change your Base
Permute(n,Base)
End
Cheers
Posted: Mon Apr 06, 2009 1:15 pm
by Mistrel
Thanks for all of the help. These solutions work great.
Posted: Mon Apr 06, 2009 4:40 pm
by pdwyer
This came up in that project Euler thing a few of us on the forums were doing a year or two ago...
Use this with any combinations of letters or numbers.
Code: Select all
Procedure.s Permutation(String$, n)
Protected i, Factorial = 1, Temp
For i = 2 To Len(String$)
Factorial * (i - 1)
*n1.Byte = @String$ + (i - ((n / Factorial) % i) - 1)
*n2.Byte = @String$ + i - 1
Temp = *n1\b
*n1\b = *n2\b
*n2\b = Temp
Next
ProcedureReturn String$
EndProcedure
MyString$ = "123456789"
cnt = 0
i = 1
Repeat
Permutation$ = Permutation(MyString$, i)
;Debug Permutation$
i + 1
cnt + 1
Until Permutation$ = MyString$
Debug cnt
Posted: Mon Apr 06, 2009 5:01 pm
by netmaestro
@einander: How do I use that to solve this?
@pdwyer: Excellent. That's just the kind of clean solution I was trying to create. I couldn't get it and I flatly refused to throw in the towel and get an algorithm off Wikipedia. I like it very much, however, it seems to be several times slower than my stupid one. On my machine, mine runs in 62 milliseconds if I time it before I do the sort/write to file, whereas yours is taking 344. I guess the difference is probably in the fact that I was paranoid of going anywhere near strings and so there's no stringhandling of any kind in mine.
Posted: Mon Apr 06, 2009 5:23 pm
by netmaestro
@pdwyer: Do you mind if I do some work on your routine and remove the strings? It'll still handle alpha or numeric data, I'm just thinking that with the strings gone that would be lighnting fast.
Posted: Mon Apr 06, 2009 5:24 pm
by pdwyer
@netmaestro, (Not my algo so I don't want to take credit), I threw in the towel and someone else in our informal little team came back with this
Performance, you are dealing with numbers and me with strings so you might be faster, debug mode might slow the string version down even further too.
what happens though if you want permutations on "ABCDEF" or "112233"?
Features are costing a bit extra I guess.
To calc the total, 2x3x4x5x6x7x8x9 will give the answer fastest, just not tell you what the permutations actually are
Posted: Mon Apr 06, 2009 6:45 pm
by Little John
Ooops! I almost forgot about the second part of the question .... how to generate the permutations.
Some time ago, I had implemented
an algorithm by Donald E. Knuth for this task. I've put it in the
Tricks 'n' Tips section now, and maybe you want to post your algorithms in that thread as well, so that later users can easier find some nice needles in this huge haystack called "forum".
Regards, Little John