How many possible combinations in a set?

Mistrel · Post by **Mistrel** » Sun Apr 05, 2009 3:04 pm

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?

netmaestro · Post by **netmaestro** » Sun Apr 05, 2009 3:15 pm

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:

Code: Select all


            N!
       -----------       
         R!(N-R)!

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:

Code: Select all


          24
       -------- = 6    
         2(2)

If by combinations you mean pairs, then plugging 9 and 2 into the equation you get:

Code: Select all



          362880
         --------- = 36    
          2(5040)

Mistrel · Post by **Mistrel** » Sun Apr 05, 2009 3:22 pm

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.

netmaestro · Post by **netmaestro** » Sun Apr 05, 2009 3:25 pm

Ok I missed the boat then. Let me consider this for a few minutes.

Mistrel · Post by **Mistrel** » Sun Apr 05, 2009 3:44 pm

Thank you for taking the time. My math skills are very rusty.

Kaeru Gaman · Post by **Kaeru Gaman** » Sun Apr 05, 2009 5:21 pm

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..

Little John · Post by **Little John** » Sun Apr 05, 2009 9:38 pm

> 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

netmaestro · Post by **netmaestro** » Mon Apr 06, 2009 12:45 am

@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.

einander · Post by **einander** » Mon Apr 06, 2009 12:41 pm

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

Mistrel · Post by **Mistrel** » Mon Apr 06, 2009 1:15 pm

Thanks for all of the help. These solutions work great.

pdwyer · Post by **pdwyer** » Mon Apr 06, 2009 4:40 pm

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

netmaestro · Post by **netmaestro** » Mon Apr 06, 2009 5:01 pm

@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.

netmaestro · Post by **netmaestro** » Mon Apr 06, 2009 5:23 pm

@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.

pdwyer · Post by **pdwyer** » Mon Apr 06, 2009 5:24 pm

@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

Little John · Post by **Little John** » Mon Apr 06, 2009 6:45 pm

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